/ TeX 1995 July / TeX CD-ROM July 1995 (Disc 1)(Walnut Creek)(1995).ISO / macros / plain / contrib / treetex / epodd.tex

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 25 20 54 68 69 73 20 69 | 73 20 65 70 6f 64 64 2e |% This i|s epodd.|
|00000010| 74 65 78 2c 20 74 68 65 | 20 64 65 73 63 72 69 70 |tex, the| descrip|
|00000020| 74 69 6f 6e 20 6f 66 20 | 74 68 65 20 74 72 65 65 |tion of |the tree|
|00000030| 74 65 78 20 6d 61 63 72 | 6f 20 70 61 63 6b 61 67 |tex macr|o packag|
|00000040| 65 20 61 73 20 69 74 20 | 77 69 6c 6c 0a 25 20 61 |e as it |will.% a|
|00000050| 70 70 65 61 72 20 69 6e | 20 45 50 2d 4f 44 44 20 |ppear in| EP-ODD |
|00000060| 69 6e 20 73 75 6d 6d 65 | 72 20 38 39 2e 20 49 74 |in summe|r 89. It|
|00000070| 20 69 73 20 69 6e 20 73 | 6f 6d 65 20 61 73 70 65 | is in s|ome aspe|
|00000080| 63 74 73 20 6d 6f 72 65 | 20 67 65 6e 65 72 61 6c |cts more| general|
|00000090| 0a 25 20 74 68 61 6e 20 | 74 72 65 65 5f 64 6f 63 |.% than |tree_doc|
|000000a0| 2e 74 65 78 20 61 6e 64 | 20 63 6f 72 72 65 63 74 |.tex and| correct|
|000000b0| 73 20 61 6e 20 65 72 72 | 6f 72 20 69 6e 20 74 68 |s an err|or in th|
|000000c0| 65 20 63 6f 6d 70 75 74 | 61 74 69 6f 6e 20 6f 66 |e comput|ation of|
|000000d0| 0a 25 20 74 68 65 20 6e | 75 6d 62 65 72 20 6f 66 |.% the n|umber of|
|000000e0| 20 72 65 67 69 73 74 65 | 72 73 20 75 73 65 64 20 | registe|rs used |
|000000f0| 62 79 20 74 72 65 65 74 | 65 78 2e 20 54 68 65 20 |by treet|ex. The |
|00000100| 75 73 65 72 20 69 6e 74 | 65 72 66 61 63 65 20 6f |user int|erface o|
|00000110| 66 0a 25 20 74 72 65 65 | 74 65 78 20 69 73 20 65 |f.% tree|tex is e|
|00000120| 78 70 6c 61 69 6e 65 64 | 20 69 6e 20 6d 6f 72 65 |xplained| in more|
|00000130| 20 64 65 74 61 69 6c 20 | 69 6e 20 74 72 65 65 5f | detail |in tree_|
|00000140| 64 6f 63 2e 74 65 78 2e | 0a 0a 5c 64 6f 63 75 6d |doc.tex.|..\docum|
|00000150| 65 6e 74 73 74 79 6c 65 | 5b 31 32 70 74 2c 66 75 |entstyle|[12pt,fu|
|00000160| 6c 6c 70 61 67 65 5d 7b | 61 72 74 69 63 6c 65 7d |llpage]{|article}|
|00000170| 0a 0a 5c 63 6c 75 62 70 | 65 6e 61 6c 74 79 3d 31 |..\clubp|enalty=1|
|00000180| 30 30 30 30 0a 5c 77 69 | 64 6f 77 70 65 6e 61 6c |0000.\wi|dowpenal|
|00000190| 74 79 3d 31 30 30 30 30 | 0a 0a 5c 64 65 66 5c 61 |ty=10000|..\def\a|
|000001a0| 64 64 63 6f 6e 74 65 6e | 74 73 6c 69 6e 65 23 31 |ddconten|tsline#1|
|000001b0| 23 32 23 33 7b 5c 72 65 | 6c 61 78 7d 25 20 53 6f |#2#3{\re|lax}% So|
|000001c0| 6d 65 20 63 61 70 74 69 | 6f 6e 73 20 61 72 65 20 |me capti|ons are |
|000001d0| 74 6f 6f 20 6c 6f 6e 67 | 20 66 6f 72 20 73 6f 6d |too long| for som|
|000001e0| 65 0a 20 20 20 20 20 25 | 20 54 65 58 20 69 6e 73 |e.     %| TeX ins|
|000001f0| 74 61 6c 6c 61 74 69 6f | 6e 73 20 28 62 75 66 66 |tallatio|ns (buff|
|00000200| 65 72 20 73 69 7a 65 20 | 74 6f 6f 20 73 6d 61 6c |er size |too smal|
|00000210| 6c 29 0a 0a 5c 6e 65 77 | 65 6e 76 69 72 6f 6e 6d |l)..\new|environm|
|00000220| 65 6e 74 7b 6c 65 6d 6d | 61 7d 7b 5c 62 65 67 69 |ent{lemm|a}{\begi|
|00000230| 6e 67 72 6f 75 70 5c 73 | 61 6d 65 70 61 67 65 5c |ngroup\s|amepage\|
|00000240| 62 65 67 69 6e 7b 6c 65 | 6d 6d 6d 61 7d 5c 20 7d |begin{le|mmma}\ }|
|00000250| 7b 5c 65 6e 64 7b 6c 65 | 6d 6d 6d 61 7d 25 0a 20 |{\end{le|mmma}%. |
|00000260| 20 20 20 20 5c 65 6e 64 | 67 72 6f 75 70 7d 0a 5c |    \end|group}.\|
|00000270| 6e 65 77 74 68 65 6f 72 | 65 6d 7b 6c 65 6d 6d 6d |newtheor|em{lemmm|
|00000280| 61 7d 7b 4c 65 6d 6d 61 | 7d 5b 73 65 63 74 69 6f |a}{Lemma|}[sectio|
|00000290| 6e 5d 0a 5c 6e 65 77 65 | 6e 76 69 72 6f 6e 6d 65 |n].\newe|nvironme|
|000002a0| 6e 74 7b 70 72 6f 6f 66 | 7d 7b 5c 62 65 67 69 6e |nt{proof|}{\begin|
|000002b0| 7b 70 72 6f 6f 6f 66 7d | 5c 72 6d 5c 20 5c 6e 6f |{prooof}|\rm\ \no|
|000002c0| 70 61 67 65 62 72 65 61 | 6b 7d 7b 5c 65 6e 64 7b |pagebrea|k}{\end{|
|000002d0| 70 72 6f 6f 6f 66 7d 7d | 0a 5c 6e 65 77 63 6f 6d |prooof}}|.\newcom|
|000002e0| 6d 61 6e 64 7b 5c 70 72 | 6f 6f 66 65 6e 64 7d 7b |mand{\pr|oofend}{|
|000002f0| 5c 71 71 75 61 64 5c 69 | 66 6d 6d 6f 64 65 5c 42 |\qquad\i|fmmode\B|
|00000300| 6f 78 5c 65 6c 73 65 24 | 5c 42 6f 78 24 5c 66 69 |ox\else$|\Box$\fi|
|00000310| 7d 0a 5c 6e 65 77 74 68 | 65 6f 72 65 6d 7b 70 72 |}.\newth|eorem{pr|
|00000320| 6f 6f 6f 66 7d 7b 50 72 | 6f 6f 66 7d 0a 5c 72 65 |ooof}{Pr|oof}.\re|
|00000330| 6e 65 77 63 6f 6d 6d 61 | 6e 64 7b 5c 74 68 65 70 |newcomma|nd{\thep|
|00000340| 72 6f 6f 6f 66 7d 7b 7d | 20 20 20 25 20 6d 61 6b |rooof}{}|   % mak|
|00000350| 65 73 20 73 68 75 72 65 | 20 74 68 61 74 20 70 72 |es shure| that pr|
|00000360| 6f 6f 6f 66 20 64 6f 65 | 73 6e 27 74 20 67 65 74 |ooof doe|sn't get|
|00000370| 20 6e 75 6d 62 65 72 73 | 0a 5c 6e 65 77 65 6e 76 | numbers|.\newenv|
|00000380| 69 72 6f 6e 6d 65 6e 74 | 7b 46 69 67 75 72 65 7d |ironment|{Figure}|
|00000390| 7b 5c 62 65 67 69 6e 7b | 66 69 67 75 72 65 7d 5c |{\begin{|figure}\|
|000003a0| 76 73 70 61 63 65 7b 31 | 5c 62 61 73 65 6c 69 6e |vspace{1|\baselin|
|000003b0| 65 73 6b 69 70 7d 7d 25 | 0a 20 20 20 20 20 20 20 |eskip}}%|.       |
|000003c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000003d0| 7b 5c 76 73 70 61 63 65 | 7b 31 5c 62 61 73 65 6c |{\vspace|{1\basel|
|000003e0| 69 6e 65 73 6b 69 70 7d | 5c 65 6e 64 7b 66 69 67 |ineskip}|\end{fig|
|000003f0| 75 72 65 7d 7d 0a 5c 6e | 65 77 6c 65 6e 67 74 68 |ure}}.\n|ewlength|
|00000400| 7b 5c 66 69 67 73 70 61 | 63 65 7d 20 20 20 20 20 |{\figspa|ce}     |
|00000410| 20 20 20 20 25 20 73 70 | 61 63 65 20 62 65 74 77 |    % sp|ace betw|
|00000420| 65 65 6e 20 66 69 67 75 | 72 65 73 20 69 6e 20 61 |een figu|res in a|
|00000430| 20 73 69 6e 67 6c 65 0a | 5c 73 65 74 6c 65 6e 67 | single.|\setleng|
|00000440| 74 68 7b 5c 66 69 67 73 | 70 61 63 65 7d 7b 33 30 |th{\figs|pace}{30|
|00000450| 70 74 7d 20 20 20 25 20 | 46 69 67 75 72 65 20 65 |pt}   % |Figure e|
|00000460| 6e 76 69 72 6f 6e 6d 65 | 6e 74 0a 0a 5c 6e 65 77 |nvironme|nt..\new|
|00000470| 63 6f 6d 6d 61 6e 64 7b | 5c 76 61 72 7d 5b 31 5d |command{|\var}[1]|
|00000480| 7b 7b 5c 69 74 20 23 31 | 5c 2f 7d 7d 20 20 20 20 |{{\it #1|\/}}    |
|00000490| 20 25 20 75 73 65 20 69 | 74 20 66 6f 72 20 6e 61 | % use i|t for na|
|000004a0| 6d 65 73 20 6f 66 20 76 | 61 72 69 61 62 6c 65 73 |mes of v|ariables|
|000004b0| 0a 5c 6e 65 77 63 6f 6d | 6d 61 6e 64 7b 5c 65 6d |.\newcom|mand{\em|
|000004c0| 70 68 7d 5b 31 5d 7b 7b | 5c 65 6d 20 23 31 5c 2f |ph}[1]{{|\em #1\/|
|000004d0| 7d 7d 20 20 20 20 25 20 | 75 73 65 20 69 74 20 66 |}}    % |use it f|
|000004e0| 6f 72 20 65 6d 70 68 61 | 7a 69 64 65 64 20 74 65 |or empha|zided te|
|000004f0| 78 74 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |xt.     |        |
|00000500| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000510| 20 20 20 20 20 20 20 20 | 25 20 28 54 68 69 73 20 |        |% (This |
|00000520| 6e 6f 74 69 6f 6e 20 73 | 74 69 63 6b 73 20 74 6f |notion s|ticks to|
|00000530| 20 74 68 65 0a 20 20 20 | 20 20 20 20 20 20 20 20 | the.   |        |
|00000540| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000550| 20 20 20 20 20 20 20 20 | 20 20 25 20 61 70 70 6c |        |  % appl|
|00000560| 69 63 61 74 69 76 65 20 | 73 74 79 6c 65 20 6f 66 |icative |style of|
|00000570| 20 6d 61 72 6b 75 70 2e | 29 0a 5c 72 65 6e 65 77 | markup.|).\renew|
|00000580| 63 6f 6d 6d 61 6e 64 7b | 5c 4f 7d 7b 7b 5c 72 6d |command{|\O}{{\rm|
|00000590| 20 4f 7d 7d 20 20 20 20 | 20 20 20 20 20 20 20 25 | O}}    |       %|
|000005a0| 20 4f 2d 6e 6f 74 61 74 | 69 6f 6e 2c 20 61 6c 73 | O-notat|ion, als|
|000005b0| 6f 20 66 6f 72 20 6d 61 | 74 68 20 6d 6f 64 65 0a |o for ma|th mode.|
|000005c0| 5c 6e 65 77 63 6f 6d 6d | 61 6e 64 7b 5c 54 7d 7b |\newcomm|and{\T}{|
|000005d0| 7b 5c 63 61 6c 20 54 7d | 7d 20 20 20 20 20 20 20 |{\cal T}|}       |
|000005e0| 20 20 20 20 20 25 20 74 | 68 65 20 73 65 74 20 54 |     % t|he set T|
|000005f0| 20 69 6e 20 6d 61 74 68 | 20 6d 6f 64 65 0a 5c 6e | in math| mode.\n|
|00000600| 65 77 63 6f 6d 6d 61 6e | 64 7b 5c 54 72 65 65 54 |ewcomman|d{\TreeT|
|00000610| 65 58 7d 7b 54 72 65 65 | 5c 54 65 58 7d 0a 5c 6e |eX}{Tree|\TeX}.\n|
|00000620| 65 77 63 6f 6d 6d 61 6e | 64 7b 5c 66 69 67 7d 5b |ewcomman|d{\fig}[|
|00000630| 31 5d 7b 46 69 67 75 72 | 65 7e 5c 72 65 66 7b 23 |1]{Figur|e~\ref{#|
|00000640| 31 7d 7d 0a 5c 6c 65 74 | 5c 70 5c 70 61 72 0a 0a |1}}.\let|\p\par..|
|00000650| 5c 69 6e 70 75 74 20 74 | 72 65 65 74 65 78 0a 5c |\input t|reetex.\|
|00000660| 54 72 65 65 73 74 79 6c | 65 7b 5c 76 64 69 73 74 |Treestyl|e{\vdist|
|00000670| 7b 32 30 70 74 7d 5c 6d | 69 6e 73 65 70 7b 31 36 |{20pt}\m|insep{16|
|00000680| 70 74 7d 7d 0a 5c 64 75 | 6d 6d 79 68 61 6c 66 63 |pt}}.\du|mmyhalfc|
|00000690| 65 6e 74 65 72 64 69 6d | 40 6e 3d 32 70 74 0a 0a |enterdim|@n=2pt..|
|000006a0| 25 20 5c 64 65 66 5c 54 | 72 65 65 23 31 5c 65 6e |% \def\T|ree#1\en|
|000006b0| 64 23 32 7b 5c 65 6e 64 | 7b 54 72 65 65 7d 7d 20 |d#2{\end|{Tree}} |
|000006c0| 20 25 20 54 72 65 65 73 | 20 61 72 65 20 6e 6f 74 | % Trees| are not|
|000006d0| 20 70 72 6f 63 65 73 73 | 65 64 0a 25 20 5c 6c 65 | process|ed.% \le|
|000006e0| 74 5c 65 6e 64 54 72 65 | 65 5c 72 65 6c 61 78 20 |t\endTre|e\relax |
|000006f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000700| 20 25 0a 0a 5c 64 65 66 | 5c 4e 6f 64 65 28 23 31 | %..\def|\Node(#1|
|00000710| 2c 23 32 29 7b 5c 70 75 | 74 28 23 31 2c 23 32 29 |,#2){\pu|t(#1,#2)|
|00000720| 7b 5c 63 69 72 63 6c 65 | 2a 7b 34 7d 7d 7d 0a 5c |{\circle|*{4}}}.\|
|00000730| 64 65 66 5c 45 64 67 65 | 28 23 31 2c 23 32 2c 23 |def\Edge|(#1,#2,#|
|00000740| 33 2c 23 34 2c 23 35 29 | 7b 5c 70 75 74 28 23 31 |3,#4,#5)|{\put(#1|
|00000750| 2c 23 32 29 7b 5c 6c 69 | 6e 65 28 23 33 2c 23 34 |,#2){\li|ne(#3,#4|
|00000760| 29 7b 23 35 7d 7d 7d 0a | 0a 5c 64 65 66 5c 65 6e |){#5}}}.|.\def\en|
|00000770| 6f 64 65 7b 5c 6e 6f 64 | 65 7b 5c 65 78 74 65 72 |ode{\nod|e{\exter|
|00000780| 6e 61 6c 5c 74 79 70 65 | 7b 64 6f 74 7d 7d 7d 0a |nal\type|{dot}}}.|
|00000790| 5c 64 65 66 5c 69 6e 6f | 64 65 7b 5c 6e 6f 64 65 |\def\ino|de{\node|
|000007a0| 7b 5c 74 79 70 65 7b 64 | 6f 74 7d 7d 7d 0a 0a 5c |{\type{d|ot}}}..\|
|000007b0| 64 65 66 5c 65 7b 5c 6e | 6f 64 65 7b 5c 65 78 74 |def\e{\n|ode{\ext|
|000007c0| 65 72 6e 61 6c 5c 74 79 | 70 65 7b 64 6f 74 7d 7d |ernal\ty|pe{dot}}|
|000007d0| 7d 0a 5c 64 65 66 5c 69 | 7b 5c 6e 6f 64 65 7b 5c |}.\def\i|{\node{\|
|000007e0| 74 79 70 65 7b 64 6f 74 | 7d 7d 7d 0a 5c 64 65 66 |type{dot|}}}.\def|
|000007f0| 5c 69 6c 7b 5c 6e 6f 64 | 65 7b 5c 74 79 70 65 7b |\il{\nod|e{\type{|
|00000800| 64 6f 74 7d 5c 6c 65 66 | 74 6f 6e 6c 79 7d 7d 0a |dot}\lef|tonly}}.|
|00000810| 5c 64 65 66 5c 69 72 7b | 5c 6e 6f 64 65 7b 5c 74 |\def\ir{|\node{\t|
|00000820| 79 70 65 7b 64 6f 74 7d | 5c 72 69 67 68 74 6f 6e |ype{dot}|\righton|
|00000830| 6c 79 7d 7d 0a 0a 5c 6e | 65 77 63 6f 6d 6d 61 6e |ly}}..\n|ewcomman|
|00000840| 64 7b 5c 73 74 61 63 6b | 7d 5b 33 5d 7b 25 0a 20 |d{\stack|}[3]{%. |
|00000850| 20 20 20 20 5c 76 74 6f | 70 7b 5c 73 65 74 74 6f |    \vto|p{\setto|
|00000860| 77 69 64 74 68 7b 5c 68 | 73 69 7a 65 7d 7b 23 31 |width{\h|size}{#1|
|00000870| 7d 25 0a 20 20 20 20 20 | 5c 73 65 74 6c 65 6e 67 |}%.     |\setleng|
|00000880| 74 68 7b 5c 6c 65 66 74 | 73 6b 69 70 7d 7b 30 70 |th{\left|skip}{0p|
|00000890| 74 20 70 6c 75 73 20 31 | 66 69 6c 6c 7d 25 0a 20 |t plus 1|fill}%. |
|000008a0| 20 20 20 20 5c 73 65 74 | 6c 65 6e 67 74 68 7b 5c |    \set|length{\|
|000008b0| 62 61 73 65 6c 69 6e 65 | 73 6b 69 70 7d 7b 23 32 |baseline|skip}{#2|
|000008c0| 7d 23 33 7d 7d 0a 0a 5c | 6c 65 74 5c 6d 75 6c 74 |}#3}}..\|let\mult|
|000008d0| 69 63 5c 6d 75 6c 74 69 | 63 6f 6c 75 6d 6e 0a 0a |ic\multi|column..|
|000008e0| 5c 6e 65 77 6c 65 6e 67 | 74 68 7b 5c 68 64 7d 20 |\newleng|th{\hd} |
|000008f0| 25 20 68 69 64 64 65 6e | 20 64 69 67 69 74 0a 5c |% hidden| digit.\|
|00000900| 73 65 74 62 6f 78 30 5c | 68 62 6f 78 7b 31 7d 0a |setbox0\|hbox{1}.|
|00000910| 5c 73 65 74 74 6f 77 69 | 64 74 68 7b 5c 68 64 7d |\settowi|dth{\hd}|
|00000920| 7b 5c 75 73 65 62 6f 78 | 7b 30 7d 7d 0a 5c 6e 65 |{\usebox|{0}}.\ne|
|00000930| 77 63 6f 6d 6d 61 6e 64 | 7b 5c 64 73 7d 7b 5c 68 |wcommand|{\ds}{\h|
|00000940| 73 70 61 63 65 7b 5c 68 | 64 7d 7d 20 25 20 64 69 |space{\h|d}} % di|
|00000950| 67 69 74 20 73 70 61 63 | 65 0a 0a 5c 6e 65 77 63 |git spac|e..\newc|
|00000960| 6f 6d 6d 61 6e 64 7b 5c | 63 63 6f 6c 7d 5b 31 5d |ommand{\|ccol}[1]|
|00000970| 7b 5c 6d 75 6c 74 69 63 | 6f 6c 75 6d 6e 7b 31 7d |{\multic|olumn{1}|
|00000980| 7b 63 7d 7b 23 31 7d 7d | 0a 0a 5c 68 79 70 68 65 |{c}{#1}}|..\hyphe|
|00000990| 6e 61 74 69 6f 6e 7b 70 | 6f 73 74 2d 6f 72 2d 64 |nation{p|ost-or-d|
|000009a0| 65 72 20 73 79 6d 2d 62 | 6f 6c 20 4b 61 72 6c 73 |er sym-b|ol Karls|
|000009b0| 2d 72 75 68 65 20 62 6f | 6f 6c 2d 65 61 6e 7d 0a |-ruhe bo|ol-ean}.|
|000009c0| 0a 5c 62 65 67 69 6e 7b | 64 6f 63 75 6d 65 6e 74 |.\begin{|document|
|000009d0| 7d 0a 0a 5c 62 69 62 6c | 69 6f 67 72 61 70 68 79 |}..\bibl|iography|
|000009e0| 73 74 79 6c 65 7b 70 6c | 61 69 6e 7d 0a 0a 5c 74 |style{pl|ain}..\t|
|000009f0| 69 74 6c 65 7b 44 72 61 | 77 69 6e 67 20 54 72 65 |itle{Dra|wing Tre|
|00000a00| 65 73 20 4e 69 63 65 6c | 79 20 77 69 74 68 20 5c |es Nicel|y with \|
|00000a10| 54 65 58 5c 74 68 61 6e | 6b 73 7b 54 68 69 73 20 |TeX\than|ks{This |
|00000a20| 77 6f 72 6b 20 77 61 73 | 20 73 75 70 70 6f 72 74 |work was| support|
|00000a30| 65 64 20 62 79 0a 20 20 | 20 20 20 61 20 4e 61 74 |ed by.  |   a Nat|
|00000a40| 75 72 61 6c 20 53 63 69 | 65 6e 63 65 73 20 61 6e |ural Sci|ences an|
|00000a50| 64 20 45 6e 67 69 6e 65 | 65 72 69 6e 67 20 52 65 |d Engine|ering Re|
|00000a60| 73 65 61 72 63 68 20 43 | 6f 75 6e 63 69 6c 20 6f |search C|ouncil o|
|00000a70| 66 20 43 61 6e 61 64 61 | 0a 20 20 20 20 20 47 72 |f Canada|.     Gr|
|00000a80| 61 6e 74 7e 41 2d 35 36 | 39 32 2c 20 61 20 44 65 |ant~A-56|92, a De|
|00000a90| 75 74 73 63 68 65 20 46 | 6f 72 73 63 68 75 6e 67 |utsche F|orschung|
|00000aa0| 73 67 65 6d 65 69 6e 73 | 63 68 61 66 74 20 47 72 |sgemeins|chaft Gr|
|00000ab0| 61 6e 74 7e 53 74 6f 31 | 36 37 2f 31 2d 31 2c 0a |ant~Sto1|67/1-1,.|
|00000ac0| 20 20 20 20 20 61 6e 64 | 20 61 20 67 72 61 6e 74 |     and| a grant|
|00000ad0| 20 66 72 6f 6d 20 74 68 | 65 20 49 6e 66 6f 72 6d | from th|e Inform|
|00000ae0| 61 74 69 6f 6e 20 54 65 | 63 68 6e 6f 6c 6f 67 79 |ation Te|chnology|
|00000af0| 20 52 65 73 65 61 72 63 | 68 20 20 43 65 6e 74 72 | Researc|h  Centr|
|00000b00| 65 2e 0a 20 20 20 20 20 | 49 74 20 77 61 73 20 62 |e..     |It was b|
|00000b10| 65 67 75 6e 20 64 75 72 | 69 6e 67 20 74 68 65 20 |egun dur|ing the |
|00000b20| 66 69 72 73 74 20 61 75 | 74 68 6f 72 27 73 20 73 |first au|thor's s|
|00000b30| 74 61 79 20 77 69 74 68 | 0a 20 20 20 20 20 74 68 |tay with|.     th|
|00000b40| 65 20 44 61 74 61 20 53 | 74 72 75 63 74 75 72 69 |e Data S|tructuri|
|00000b50| 6e 67 20 47 72 6f 75 70 | 20 69 6e 20 57 61 74 65 |ng Group| in Wate|
|00000b60| 72 6c 6f 6f 2e 7d 7d 0a | 5c 61 75 74 68 6f 72 7b |rloo.}}.|\author{|
|00000b70| 41 6e 6e 65 20 42 72 5c | 22 75 67 67 65 6d 61 6e |Anne Br\|"uggeman|
|00000b80| 6e 2d 4b 6c 65 69 6e 5c | 74 68 61 6e 6b 73 7b 49 |n-Klein\|thanks{I|
|00000b90| 6e 73 74 69 74 75 74 20 | 66 5c 22 75 72 20 49 6e |nstitut |f\"ur In|
|00000ba0| 66 6f 72 6d 61 74 69 6b | 2c 0a 20 20 20 20 20 55 |formatik|,.     U|
|00000bb0| 6e 69 76 65 72 73 69 74 | 5c 22 61 74 20 46 72 65 |niversit|\"at Fre|
|00000bc0| 69 62 75 72 67 2c 20 52 | 68 65 69 6e 73 74 72 2e |iburg, R|heinstr.|
|00000bd0| 7e 31 30 2d 2d 31 32 2c | 20 37 38 30 30 7e 46 72 |~10--12,| 7800~Fr|
|00000be0| 65 69 62 75 72 67 2c 0a | 20 20 20 20 20 57 65 73 |eiburg,.|     Wes|
|00000bf0| 74 7e 47 65 72 6d 61 6e | 79 7d 5c 20 5c 61 6e 64 |t~German|y}\ \and|
|00000c00| 20 44 65 72 69 63 6b 20 | 57 6f 6f 64 5c 74 68 61 | Derick |Wood\tha|
|00000c10| 6e 6b 73 7b 44 61 74 61 | 0a 20 20 20 20 20 53 74 |nks{Data|.     St|
|00000c20| 72 75 63 74 75 72 69 6e | 67 20 47 72 6f 75 70 2c |ructurin|g Group,|
|00000c30| 20 44 65 70 61 72 74 6d | 65 6e 74 20 6f 66 20 43 | Departm|ent of C|
|00000c40| 6f 6d 70 75 74 65 72 20 | 53 63 69 65 6e 63 65 2c |omputer |Science,|
|00000c50| 20 55 6e 69 76 65 72 73 | 69 74 79 20 6f 66 0a 20 | Univers|ity of. |
|00000c60| 20 20 20 20 57 61 74 65 | 72 6c 6f 6f 2c 20 57 61 |    Wate|rloo, Wa|
|00000c70| 74 65 72 6c 6f 6f 2c 20 | 4f 6e 74 61 72 69 6f 20 |terloo, |Ontario |
|00000c80| 4e 32 4c 7e 33 47 31 2c | 20 43 61 6e 61 64 61 7d |N2L~3G1,| Canada}|
|00000c90| 7d 0a 5c 64 61 74 65 7b | 7d 0a 5c 6d 61 6b 65 74 |}.\date{|}.\maket|
|00000ca0| 69 74 6c 65 0a 0a 5c 62 | 65 67 69 6e 7b 61 62 73 |itle..\b|egin{abs|
|00000cb0| 74 72 61 63 74 7d 0a 0a | 57 65 20 70 72 65 73 65 |tract}..|We prese|
|00000cc0| 6e 74 20 61 20 6e 65 77 | 20 73 6f 6c 75 74 69 6f |nt a new| solutio|
|00000cd0| 6e 20 74 6f 20 74 68 65 | 20 74 72 65 65 20 64 72 |n to the| tree dr|
|00000ce0| 61 77 69 6e 67 20 70 72 | 6f 62 6c 65 6d 20 74 68 |awing pr|oblem th|
|00000cf0| 61 74 0a 69 6e 74 65 67 | 72 61 74 65 73 20 61 6e |at.integ|rates an|
|00000d00| 20 65 78 63 65 6c 6c 65 | 6e 74 20 74 72 65 65 20 | excelle|nt tree |
|00000d10| 64 72 61 77 69 6e 67 20 | 61 6c 67 6f 72 69 74 68 |drawing |algorith|
|00000d20| 6d 20 69 6e 74 6f 20 6f | 6e 65 20 6f 66 20 74 68 |m into o|ne of th|
|00000d30| 65 20 62 65 73 74 20 74 | 65 78 74 0a 70 72 6f 63 |e best t|ext.proc|
|00000d40| 65 73 73 69 6e 67 20 73 | 79 73 74 65 6d 73 20 61 |essing s|ystems a|
|00000d50| 76 61 69 6c 61 62 6c 65 | 2e 20 4d 6f 72 65 20 70 |vailable|. More p|
|00000d60| 72 65 63 69 73 65 6c 79 | 2c 20 77 65 20 70 72 65 |recisely|, we pre|
|00000d70| 73 65 6e 74 20 61 20 5c | 54 65 58 7b 7d 20 6d 61 |sent a \|TeX{} ma|
|00000d80| 63 72 6f 20 70 61 63 6b | 61 67 65 0a 63 61 6c 6c |cro pack|age.call|
|00000d90| 65 64 20 5c 54 72 65 65 | 54 65 58 7b 7d 20 74 68 |ed \Tree|TeX{} th|
|00000da0| 61 74 20 70 72 6f 64 75 | 63 65 73 20 64 72 61 77 |at produ|ces draw|
|00000db0| 69 6e 67 73 20 6f 66 20 | 74 72 65 65 73 20 66 72 |ings of |trees fr|
|00000dc0| 6f 6d 20 61 20 70 75 72 | 65 6c 79 20 6c 6f 67 69 |om a pur|ely logi|
|00000dd0| 63 61 6c 0a 64 65 73 63 | 72 69 70 74 69 6f 6e 2e |cal.desc|ription.|
|00000de0| 20 4f 75 72 20 61 70 70 | 72 6f 61 63 68 20 68 61 | Our app|roach ha|
|00000df0| 73 20 74 68 72 65 65 20 | 61 64 76 61 6e 74 61 67 |s three |advantag|
|00000e00| 65 73 3a 20 4c 61 62 65 | 6c 73 0a 66 6f 72 20 6e |es: Labe|ls.for n|
|00000e10| 6f 64 65 73 20 63 61 6e | 20 62 65 20 68 61 6e 64 |odes can| be hand|
|00000e20| 6c 65 64 20 69 6e 20 61 | 20 72 65 61 73 6f 6e 61 |led in a| reasona|
|00000e30| 62 6c 65 20 77 61 79 3b | 20 70 6f 72 74 69 6e 67 |ble way;| porting|
|00000e40| 0a 5c 54 72 65 65 54 65 | 58 7b 7d 20 74 6f 20 61 |.\TreeTe|X{} to a|
|00000e50| 6e 79 20 73 69 74 65 20 | 72 75 6e 6e 69 6e 67 20 |ny site |running |
|00000e60| 5c 54 65 58 7b 7d 20 69 | 73 20 61 20 74 72 69 76 |\TeX{} i|s a triv|
|00000e70| 69 61 6c 20 6f 70 65 72 | 61 74 69 6f 6e 3b 20 61 |ial oper|ation; a|
|00000e80| 6e 64 0a 6d 6f 64 75 6c | 61 72 69 74 79 20 69 6e |nd.modul|arity in|
|00000e90| 20 74 68 65 20 64 65 73 | 63 72 69 70 74 69 6f 6e | the des|cription|
|00000ea0| 20 6f 66 20 61 20 74 72 | 65 65 20 61 6e 64 20 5c | of a tr|ee and \|
|00000eb0| 54 65 58 7b 7d 27 73 20 | 6d 61 63 72 6f 20 63 61 |TeX{}'s |macro ca|
|00000ec0| 70 61 62 69 6c 69 74 69 | 65 73 0a 61 6c 6c 6f 77 |pabiliti|es.allow|
|00000ed0| 20 66 6f 72 20 6c 69 62 | 72 61 72 69 65 73 20 6f | for lib|raries o|
|00000ee0| 66 20 73 75 62 74 72 65 | 65 73 20 61 6e 64 20 74 |f subtre|es and t|
|00000ef0| 72 65 65 20 63 6c 61 73 | 73 65 73 2e 0a 0a 49 6e |ree clas|ses...In|
|00000f00| 20 61 64 64 69 74 69 6f | 6e 2c 20 5c 54 72 65 65 | additio|n, \Tree|
|00000f10| 54 65 58 7b 7d 20 68 61 | 73 20 61 6e 20 6f 70 74 |TeX{} ha|s an opt|
|00000f20| 69 6f 6e 20 74 68 61 74 | 20 70 72 6f 64 75 63 65 |ion that| produce|
|00000f30| 73 0a 64 72 61 77 69 6e | 67 73 20 74 68 61 74 20 |s.drawin|gs that |
|00000f40| 6d 61 6b 65 20 74 68 65 | 0a 5c 65 6d 70 68 7b 73 |make the|.\emph{s|
|00000f50| 74 72 75 63 74 75 72 65 | 7d 20 6f 66 20 74 68 65 |tructure|} of the|
|00000f60| 20 74 72 65 65 73 20 6d | 6f 72 65 20 6f 62 76 69 | trees m|ore obvi|
|00000f70| 6f 75 73 20 74 6f 20 74 | 68 65 20 68 75 6d 61 6e |ous to t|he human|
|00000f80| 20 65 79 65 2c 0a 65 76 | 65 6e 20 74 68 6f 75 67 | eye,.ev|en thoug|
|00000f90| 68 20 74 68 65 79 20 6d | 61 79 20 6e 6f 74 20 62 |h they m|ay not b|
|00000fa0| 65 20 61 73 20 61 65 73 | 74 68 65 74 69 63 61 6c |e as aes|thetical|
|00000fb0| 6c 79 20 70 6c 65 61 73 | 69 6e 67 2e 0a 0a 5c 65 |ly pleas|ing...\e|
|00000fc0| 6e 64 7b 61 62 73 74 72 | 61 63 74 7d 0a 0a 5c 73 |nd{abstr|act}..\s|
|00000fd0| 65 63 74 69 6f 6e 7b 49 | 6e 74 72 6f 64 75 63 74 |ection{I|ntroduct|
|00000fe0| 69 6f 6e 7d 0a 0a 54 68 | 65 20 70 72 6f 62 6c 65 |ion}..Th|e proble|
|00000ff0| 6d 20 6f 66 20 73 75 63 | 63 65 73 73 66 75 6c 6c |m of suc|cessfull|
|00001000| 79 20 69 6e 74 65 67 72 | 61 74 69 6e 67 20 70 69 |y integr|ating pi|
|00001010| 63 74 75 72 65 73 20 61 | 6e 64 20 74 65 78 74 20 |ctures a|nd text |
|00001020| 69 6e 20 61 0a 64 6f 63 | 75 6d 65 6e 74 20 70 72 |in a.doc|ument pr|
|00001030| 6f 63 65 73 73 69 6e 67 | 20 65 6e 76 69 72 6f 6e |ocessing| environ|
|00001040| 6d 65 6e 74 20 69 73 20 | 74 61 6e 74 61 6c 69 7a |ment is |tantaliz|
|00001050| 69 6e 67 20 61 6e 64 20 | 64 69 66 66 69 63 75 6c |ing and |difficul|
|00001060| 74 2e 0a 41 6c 74 68 6f | 75 67 68 20 74 68 65 72 |t..Altho|ugh ther|
|00001070| 65 20 61 72 65 20 73 79 | 73 74 65 6d 73 20 61 76 |e are sy|stems av|
|00001080| 61 69 6c 61 62 6c 65 20 | 74 68 61 74 20 61 6c 6c |ailable |that all|
|00001090| 6f 77 20 73 75 63 68 20 | 69 6e 74 65 67 72 61 74 |ow such |integrat|
|000010a0| 69 6f 6e 2c 20 74 68 65 | 79 0a 66 61 6c 6c 20 73 |ion, the|y.fall s|
|000010b0| 68 6f 72 74 20 69 6e 20 | 6d 61 6e 79 20 77 61 79 |hort in |many way|
|000010c0| 73 2c 20 75 73 75 61 6c | 6c 79 20 69 6e 20 64 6f |s, usual|ly in do|
|000010d0| 63 75 6d 65 6e 74 20 71 | 75 61 6c 69 74 79 2e 20 |cument q|uality. |
|000010e0| 46 75 72 74 68 65 72 6d | 6f 72 65 2c 0a 6d 6f 73 |Furtherm|ore,.mos|
|000010f0| 74 20 61 75 74 68 6f 72 | 73 20 75 73 69 6e 67 20 |t author|s using |
|00001100| 64 6f 63 75 6d 65 6e 74 | 20 20 70 72 65 70 61 72 |document|  prepar|
|00001110| 61 74 69 6f 6e 20 73 79 | 73 74 65 6d 73 20 61 72 |ation sy|stems ar|
|00001120| 65 20 6e 65 69 74 68 65 | 72 20 62 6f 6f 6b 20 0a |e neithe|r book .|
|00001130| 64 65 73 69 67 6e 65 72 | 73 20 6e 6f 72 20 67 72 |designer|s nor gr|
|00001140| 61 70 68 69 63 20 61 72 | 74 69 73 74 73 2e 20 20 |aphic ar|tists.  |
|00001150| 4a 75 73 74 20 61 73 20 | 6d 6f 64 65 72 6e 20 64 |Just as |modern d|
|00001160| 6f 63 75 6d 65 6e 74 20 | 70 72 65 70 61 72 61 74 |ocument |preparat|
|00001170| 69 6f 6e 0a 73 79 73 74 | 65 6d 73 20 64 6f 20 6e |ion.syst|ems do n|
|00001180| 6f 74 20 65 78 70 65 63 | 74 20 61 6e 20 61 75 74 |ot expec|t an aut|
|00001190| 68 6f 72 20 74 6f 20 62 | 65 20 61 20 62 6f 6f 6b |hor to b|e a book|
|000011a0| 20 64 65 73 69 67 6e 65 | 72 2c 20 73 6f 20 77 65 | designe|r, so we|
|000011b0| 20 77 6f 75 6c 64 0a 70 | 72 65 66 65 72 20 74 68 | would.p|refer th|
|000011c0| 61 74 20 74 68 65 79 20 | 64 6f 20 6e 6f 74 20 65 |at they |do not e|
|000011d0| 78 70 65 63 74 20 61 6e | 20 61 75 74 68 6f 72 20 |xpect an| author |
|000011e0| 74 6f 20 62 65 20 61 20 | 67 72 61 70 68 69 63 20 |to be a |graphic |
|000011f0| 61 72 74 69 73 74 2e 20 | 54 68 65 0a 73 65 63 6f |artist. |The.seco|
|00001200| 6e 64 20 61 75 74 68 6f | 72 2c 20 57 6f 6f 64 2c |nd autho|r, Wood,|
|00001210| 20 6e 65 65 64 65 64 20 | 74 6f 20 64 72 61 77 20 | needed |to draw |
|00001220| 6d 61 6e 79 20 74 72 65 | 65 73 20 69 6e 20 61 20 |many tre|es in a |
|00001230| 73 65 72 69 65 73 20 6f | 66 20 70 61 70 65 72 73 |series o|f papers|
|00001240| 0a 6f 6e 20 74 72 65 65 | 73 20 61 6e 64 20 69 6e |.on tree|s and in|
|00001250| 20 61 20 70 72 6f 6a 65 | 63 74 65 64 20 62 6f 6f | a proje|cted boo|
|00001260| 6b 20 6f 6e 20 74 72 65 | 65 73 2e 20 54 68 69 73 |k on tre|es. This|
|00001270| 20 70 72 6f 62 6c 65 6d | 20 65 6e 61 62 6c 65 64 | problem| enabled|
|00001280| 20 75 73 0a 74 6f 20 74 | 61 63 6b 6c 65 20 74 68 | us.to t|ackle th|
|00001290| 65 20 69 6e 74 65 67 72 | 61 74 69 6f 6e 20 69 73 |e integr|ation is|
|000012a0| 73 75 65 20 66 6f 72 20 | 6f 6e 65 20 73 75 62 61 |sue for |one suba|
|000012b0| 72 65 61 20 6f 66 20 67 | 72 61 70 68 69 63 73 2c |rea of g|raphics,|
|000012c0| 20 6e 61 6d 65 6c 79 2c | 0a 74 72 65 65 20 64 72 | namely,|.tree dr|
|000012d0| 61 77 69 6e 67 2e 20 57 | 65 20 68 61 64 20 74 68 |awing. W|e had th|
|000012e0| 65 20 64 65 63 69 64 65 | 64 20 61 64 76 61 6e 74 |e decide|d advant|
|000012f0| 61 67 65 20 74 68 61 74 | 20 74 68 65 72 65 20 61 |age that| there a|
|00001300| 6c 72 65 61 64 79 20 65 | 78 69 73 74 65 64 20 67 |lready e|xisted g|
|00001310| 6f 6f 64 0a 61 6c 67 6f | 72 69 74 68 6d 73 20 74 |ood.algo|rithms t|
|00001320| 6f 20 64 72 61 77 20 74 | 72 65 65 73 20 7b 5c 65 |o draw t|rees {\e|
|00001330| 6d 20 77 69 74 68 6f 75 | 74 20 61 6e 79 20 61 75 |m withou|t any au|
|00001340| 74 68 6f 72 20 69 6e 74 | 65 72 76 65 6e 74 69 6f |thor int|erventio|
|00001350| 6e 7d 2e 0a 50 72 65 76 | 69 6f 75 73 20 65 78 70 |n}..Prev|ious exp|
|00001360| 65 72 69 65 6e 63 65 20 | 6f 66 20 74 68 65 20 69 |erience |of the i|
|00001370| 6e 74 65 67 72 61 74 69 | 6f 6e 20 6f 66 20 70 69 |ntegrati|on of pi|
|00001380| 63 74 75 72 65 73 20 61 | 6e 64 20 74 65 78 74 20 |ctures a|nd text |
|00001390| 68 61 64 20 62 65 65 6e | 0a 75 6e 69 6e 73 70 69 |had been|.uninspi|
|000013a0| 72 69 6e 67 3b 20 74 68 | 65 20 20 73 79 73 74 65 |ring; th|e  syste|
|000013b0| 6d 73 20 65 78 70 65 63 | 74 65 64 20 74 68 65 20 |ms expec|ted the |
|000013c0| 61 75 74 68 6f 72 20 74 | 6f 20 70 72 65 70 61 72 |author t|o prepar|
|000013d0| 65 20 65 61 63 68 20 70 | 69 63 74 75 72 65 0a 69 |e each p|icture.i|
|000013e0| 6e 20 74 6f 74 61 6c 2e | 20 46 6f 72 20 65 78 61 |n total.| For exa|
|000013f0| 6d 70 6c 65 2c 20 61 20 | 74 72 65 65 20 63 6f 75 |mple, a |tree cou|
|00001400| 6c 64 20 62 65 20 62 75 | 69 6c 74 20 75 70 20 66 |ld be bu|ilt up f|
|00001410| 72 6f 6d 20 73 6d 61 6c | 6c 65 72 0a 73 75 62 74 |rom smal|ler.subt|
|00001420| 72 65 65 73 20 62 75 74 | 20 74 68 65 20 72 65 6c |rees but| the rel|
|00001430| 61 74 69 76 65 20 70 6c | 61 63 65 6d 65 6e 74 20 |ative pl|acement |
|00001440| 6f 66 20 74 68 65 6d 20 | 77 61 73 20 6c 65 66 74 |of them |was left|
|00001450| 20 74 6f 20 74 68 65 20 | 61 75 74 68 6f 72 2e 0a | to the |author..|
|00001460| 54 68 69 73 20 73 69 74 | 75 61 74 69 6f 6e 20 63 |This sit|uation c|
|00001470| 6f 6e 74 69 6e 75 65 73 | 20 74 6f 20 68 6f 6c 64 |ontinues| to hold|
|00001480| 20 74 6f 64 61 79 20 77 | 69 74 68 20 74 68 65 20 | today w|ith the |
|00001490| 64 72 61 77 69 6e 67 20 | 66 61 63 69 6c 69 74 69 |drawing |faciliti|
|000014a0| 65 73 0a 61 76 61 69 6c | 61 62 6c 65 20 6f 6e 20 |es.avail|able on |
|000014b0| 6d 6f 73 74 20 70 65 72 | 73 6f 6e 61 6c 20 63 6f |most per|sonal co|
|000014c0| 6d 70 75 74 65 72 73 2c | 20 61 6e 64 2c 20 62 65 |mputers,| and, be|
|000014d0| 63 61 75 73 65 20 6f 66 | 20 74 68 69 73 2c 20 74 |cause of| this, t|
|000014e0| 68 65 0a 72 65 73 75 6c | 74 69 6e 67 20 66 69 67 |he.resul|ting fig|
|000014f0| 75 72 65 73 20 73 74 69 | 6c 6c 20 61 70 70 65 61 |ures sti|ll appea|
|00001500| 72 20 74 6f 20 62 65 20 | 60 60 68 61 6e 64 2d 64 |r to be |``hand-d|
|00001510| 72 61 77 6e 2e 27 27 20 | 41 64 64 69 74 69 6f 6e |rawn.'' |Addition|
|00001520| 61 6c 6c 79 2c 0a 74 68 | 65 79 20 61 72 65 20 6f |ally,.th|ey are o|
|00001530| 66 20 69 6e 66 65 72 69 | 6f 72 20 71 75 61 6c 69 |f inferi|or quali|
|00001540| 74 79 20 77 68 65 6e 20 | 63 6f 6d 70 61 72 65 64 |ty when |compared|
|00001550| 20 77 69 74 68 20 74 68 | 65 20 71 75 61 6c 69 74 | with th|e qualit|
|00001560| 79 20 6f 66 0a 74 68 65 | 20 73 75 72 72 6f 75 6e |y of.the| surroun|
|00001570| 64 69 6e 67 20 74 65 78 | 74 2e 0a 0a 49 6e 20 74 |ding tex|t...In t|
|00001580| 68 69 73 20 70 61 70 65 | 72 20 77 65 20 70 72 65 |his pape|r we pre|
|00001590| 73 65 6e 74 20 61 6e 20 | 65 6e 74 69 72 65 6c 79 |sent an |entirely|
|000015a0| 20 6e 65 77 20 73 6f 6c | 75 74 69 6f 6e 20 74 68 | new sol|ution th|
|000015b0| 61 74 20 69 6e 74 65 67 | 72 61 74 65 73 0a 61 20 |at integ|rates.a |
|000015c0| 74 72 65 65 20 64 72 61 | 77 69 6e 67 20 61 6c 67 |tree dra|wing alg|
|000015d0| 6f 72 69 74 68 6d 20 69 | 6e 74 6f 20 6f 6e 65 20 |orithm i|nto one |
|000015e0| 6f 66 20 74 68 65 20 62 | 65 73 74 20 74 65 78 74 |of the b|est text|
|000015f0| 20 70 72 6f 63 65 73 73 | 69 6e 67 0a 73 79 73 74 | process|ing.syst|
|00001600| 65 6d 73 20 61 76 61 69 | 6c 61 62 6c 65 2e 20 4d |ems avai|lable. M|
|00001610| 6f 72 65 20 70 72 65 63 | 69 73 65 6c 79 2c 20 77 |ore prec|isely, w|
|00001620| 65 20 20 64 65 73 63 72 | 69 62 65 20 5c 54 72 65 |e  descr|ibe \Tre|
|00001630| 65 54 65 58 7b 7d 2c 20 | 61 0a 5c 54 65 58 7b 7d |eTeX{}, |a.\TeX{}|
|00001640| 20 6d 61 63 72 6f 20 70 | 61 63 6b 61 67 65 20 74 | macro p|ackage t|
|00001650| 68 61 74 20 70 72 6f 64 | 75 63 65 73 20 61 6e 20 |hat prod|uces an |
|00001660| 61 65 73 74 68 65 74 69 | 63 61 6c 6c 79 20 70 6c |aestheti|cally pl|
|00001670| 65 61 73 69 6e 67 0a 64 | 72 61 77 69 6e 67 20 6f |easing.d|rawing o|
|00001680| 66 20 61 20 74 72 65 65 | 20 66 72 6f 6d 20 61 20 |f a tree| from a |
|00001690| 70 75 72 65 6c 79 20 6c | 6f 67 69 63 61 6c 20 64 |purely l|ogical d|
|000016a0| 65 73 63 72 69 70 74 69 | 6f 6e 2e 0a 57 65 20 6d |escripti|on..We m|
|000016b0| 61 64 65 20 74 77 6f 20 | 66 75 6e 64 61 6d 65 6e |ade two |fundamen|
|000016c0| 74 61 6c 20 64 65 73 69 | 67 6e 0a 64 65 63 69 73 |tal desi|gn.decis|
|000016d0| 69 6f 6e 73 20 74 68 61 | 74 20 68 65 61 76 69 6c |ions tha|t heavil|
|000016e0| 79 20 69 6e 66 6c 75 65 | 6e 63 65 64 20 74 68 65 |y influe|nced the|
|000016f0| 20 6d 65 74 68 6f 64 20 | 6f 66 20 69 6d 70 6c 65 | method |of imple|
|00001700| 6d 65 6e 74 61 74 69 6f | 6e 2e 0a 46 69 72 73 74 |mentatio|n..First|
|00001710| 2c 20 77 65 20 77 61 6e | 74 65 64 20 74 6f 20 61 |, we wan|ted to a|
|00001720| 6c 6c 6f 77 20 61 6e 20 | 61 75 74 68 6f 72 20 74 |llow an |author t|
|00001730| 6f 20 6c 61 62 65 6c 20 | 74 68 65 20 6e 6f 64 65 |o label |the node|
|00001740| 73 20 6f 66 20 61 20 74 | 72 65 65 2e 0a 54 68 69 |s of a t|ree..Thi|
|00001750| 73 20 64 65 63 69 73 69 | 6f 6e 20 6d 65 61 6e 73 |s decisi|on means|
|00001760| 20 74 68 61 74 20 74 68 | 65 20 74 72 65 65 20 64 | that th|e tree d|
|00001770| 72 61 77 69 6e 67 20 70 | 61 63 6b 61 67 65 20 6d |rawing p|ackage m|
|00001780| 75 73 74 20 62 65 20 61 | 62 6c 65 20 74 6f 0a 74 |ust be a|ble to.t|
|00001790| 79 70 65 73 65 74 20 6c | 61 62 65 6c 73 20 65 78 |ypeset l|abels ex|
|000017a0| 61 63 74 6c 79 20 61 73 | 20 74 68 65 79 20 77 6f |actly as| they wo|
|000017b0| 75 6c 64 20 62 65 20 74 | 79 70 65 73 65 74 20 62 |uld be t|ypeset b|
|000017c0| 79 20 74 68 65 20 74 79 | 70 65 73 65 74 74 69 6e |y the ty|pesettin|
|000017d0| 67 0a 70 72 6f 67 72 61 | 6d 2e 20 54 68 65 72 65 |g.progra|m. There|
|000017e0| 20 61 72 65 20 74 77 6f | 20 72 65 61 73 6f 6e 73 | are two| reasons|
|000017f0| 20 66 6f 72 20 74 68 69 | 73 2e 20 54 65 78 74 20 | for thi|s. Text |
|00001800| 73 68 6f 75 6c 64 20 62 | 65 20 74 79 70 65 73 65 |should b|e typese|
|00001810| 74 0a 63 6f 6e 73 69 73 | 74 65 6e 74 6c 79 2c 20 |t.consis|tently, |
|00001820| 77 68 65 72 65 76 65 72 | 20 69 74 20 61 70 70 65 |wherever| it appe|
|00001830| 61 72 73 20 69 6e 20 61 | 20 64 6f 63 75 6d 65 6e |ars in a| documen|
|00001840| 74 2c 20 61 6e 64 20 74 | 68 65 20 74 72 65 65 0a |t, and t|he tree.|
|00001850| 64 72 61 77 69 6e 67 20 | 70 72 6f 67 72 61 6d 20 |drawing |program |
|00001860| 6e 65 65 64 73 20 74 6f | 20 6b 6e 6f 77 20 74 68 |needs to| know th|
|00001870| 65 20 64 69 6d 65 6e 73 | 69 6f 6e 73 20 6f 66 20 |e dimens|ions of |
|00001880| 74 68 65 20 74 79 70 65 | 73 65 74 20 6c 61 62 65 |the type|set labe|
|00001890| 6c 73 2e 0a 53 65 63 6f | 6e 64 2c 20 77 65 20 77 |ls..Seco|nd, we w|
|000018a0| 61 6e 74 65 64 20 74 6f | 20 65 6e 73 75 72 65 20 |anted to| ensure |
|000018b0| 74 68 61 74 20 74 68 65 | 20 70 72 6f 67 72 61 6d |that the| program|
|000018c0| 20 63 6f 75 6c 64 20 62 | 65 20 70 6f 72 74 65 64 | could b|e ported|
|000018d0| 0a 65 61 73 69 6c 79 20 | 74 6f 20 6f 74 68 65 72 |.easily |to other|
|000018e0| 20 69 6e 73 74 61 6c 6c | 61 74 69 6f 6e 73 20 61 | install|ations a|
|000018f0| 6e 64 20 73 69 74 65 73 | 2c 20 73 6f 20 74 68 61 |nd sites|, so tha|
|00001900| 74 20 6f 74 68 65 72 2c | 20 70 75 74 61 74 69 76 |t other,| putativ|
|00001910| 65 0a 75 73 65 72 73 20 | 77 6f 75 6c 64 20 62 65 |e.users |would be|
|00001920| 20 61 62 6c 65 20 74 6f | 20 75 73 65 20 69 74 20 | able to| use it |
|00001930| 65 61 73 69 6c 79 2e 0a | 49 6e 64 65 65 64 2c 20 |easily..|Indeed, |
|00001940| 5c 54 72 65 65 54 65 58 | 7b 7d 20 68 61 73 20 62 |\TreeTeX|{} has b|
|00001950| 65 65 6e 20 75 73 65 64 | 20 73 75 63 63 65 73 73 |een used| success|
|00001960| 66 75 6c 6c 79 20 74 6f | 20 74 79 70 65 73 65 74 |fully to| typeset|
|00001970| 20 74 72 65 65 73 20 69 | 6e 0a 5c 63 69 74 65 7b | trees i|n.\cite{|
|00001980| 42 61 65 7a 61 54 72 65 | 65 73 7d 2c 20 5c 63 69 |BaezaTre|es}, \ci|
|00001990| 74 65 7b 4b 57 49 46 49 | 50 7d 2c 20 61 6e 64 20 |te{KWIFI|P}, and |
|000019a0| 5c 63 69 74 65 7b 4f 41 | 50 44 7d 2e 0a 0a 42 79 |\cite{OA|PD}...By|
|000019b0| 20 62 61 73 69 6e 67 20 | 6f 75 72 20 70 61 63 6b | basing |our pack|
|000019c0| 61 67 65 20 6f 6e 20 5c | 54 65 58 7b 7d 2c 20 77 |age on \|TeX{}, w|
|000019d0| 68 69 63 68 20 66 6f 72 | 20 6d 6f 72 65 20 73 75 |hich for| more su|
|000019e0| 62 6a 65 63 74 69 76 65 | 0a 72 65 61 73 6f 6e 73 |bjective|.reasons|
|000019f0| 20 77 65 20 70 72 65 66 | 65 72 72 65 64 20 6f 76 | we pref|erred ov|
|00001a00| 65 72 20 6f 74 68 65 72 | 20 74 79 70 65 73 65 74 |er other| typeset|
|00001a10| 74 69 6e 67 20 73 79 73 | 74 65 6d 73 20 73 75 63 |ting sys|tems suc|
|00001a20| 68 20 61 73 0a 74 72 6f | 66 66 2c 20 77 65 20 63 |h as.tro|ff, we c|
|00001a30| 6f 75 6c 64 20 65 6e 73 | 75 72 65 20 77 69 64 65 |ould ens|ure wide|
|00001a40| 20 69 6e 74 65 72 65 73 | 74 0a 69 6e 20 74 68 65 | interes|t.in the|
|00001a50| 20 70 61 63 6b 61 67 65 | 2e 20 42 79 20 69 6d 70 | package|. By imp|
|00001a60| 6c 65 6d 65 6e 74 69 6e | 67 20 69 74 20 61 73 20 |lementin|g it as |
|00001a70| 61 20 5c 54 65 58 7b 7d | 20 6d 61 63 72 6f 20 70 |a \TeX{}| macro p|
|00001a80| 61 63 6b 61 67 65 0a 69 | 6e 73 74 65 61 64 20 6f |ackage.i|nstead o|
|00001a90| 66 20 61 20 70 72 65 70 | 72 6f 63 65 73 73 6f 72 |f a prep|rocessor|
|00001aa0| 0a 77 65 20 6d 61 64 65 | 20 70 6f 72 74 69 6e 67 |.we made| porting|
|00001ab0| 20 74 72 69 76 69 61 6c | 20 61 6e 64 2c 20 66 75 | trivial| and, fu|
|00001ac0| 72 74 68 65 72 6d 6f 72 | 65 2c 20 74 68 69 73 20 |rthermor|e, this |
|00001ad0| 61 6c 73 6f 20 65 6e 73 | 75 72 65 64 0a 63 6f 6e |also ens|ured.con|
|00001ae0| 73 69 73 74 65 6e 63 79 | 20 6f 66 20 74 79 70 65 |sistency| of type|
|00001af0| 73 65 74 20 74 65 78 74 | 20 77 69 74 68 69 6e 20 |set text| within |
|00001b00| 61 20 64 6f 63 75 6d 65 | 6e 74 2e 0a 54 68 65 20 |a docume|nt..The |
|00001b10| 64 6f 77 6e 20 73 69 64 | 65 20 6f 66 20 74 68 69 |down sid|e of thi|
|00001b20| 73 20 64 65 63 69 73 69 | 6f 6e 20 69 73 20 74 68 |s decisi|on is th|
|00001b30| 61 74 20 77 65 20 68 61 | 64 20 20 74 6f 20 70 72 |at we ha|d  to pr|
|00001b40| 6f 67 72 61 6d 20 77 69 | 74 68 0a 5c 54 65 58 7b |ogram wi|th.\TeX{|
|00001b50| 7d 20 6d 61 63 72 6f 73 | 2c 20 6e 6f 74 20 61 6e |} macros|, not an|
|00001b60| 20 65 78 70 65 72 69 65 | 6e 63 65 20 74 6f 20 62 | experie|nce to b|
|00001b70| 65 20 72 65 63 6f 6d 6d | 65 6e 64 65 64 2c 20 61 |e recomm|ended, a|
|00001b80| 6e 64 20 77 65 20 68 61 | 64 20 74 6f 20 6c 69 76 |nd we ha|d to liv|
|00001b90| 65 0a 77 69 74 68 20 74 | 68 65 20 69 6e 68 65 72 |e.with t|he inher|
|00001ba0| 65 6e 74 20 72 65 67 69 | 73 74 65 72 20 6c 69 6d |ent regi|ster lim|
|00001bb0| 69 74 61 74 69 6f 6e 73 | 20 6f 66 20 5c 54 65 58 |itations| of \TeX|
|00001bc0| 7b 7d 2e 0a 0a 54 68 69 | 73 20 70 61 70 65 72 20 |{}...Thi|s paper |
|00001bd0| 63 6f 6e 73 69 73 74 73 | 20 6f 66 20 61 20 66 75 |consists| of a fu|
|00001be0| 72 74 68 65 72 20 6e 69 | 6e 65 20 20 73 65 63 74 |rther ni|ne  sect|
|00001bf0| 69 6f 6e 73 2e 20 49 6e | 20 53 65 63 74 69 6f 6e |ions. In| Section|
|00001c00| 73 7e 32 2c 20 33 20 61 | 6e 64 7e 34 2c 0a 77 65 |s~2, 3 a|nd~4,.we|
|00001c10| 20 64 69 73 63 75 73 73 | 20 74 68 65 20 61 65 73 | discuss| the aes|
|00001c20| 74 68 65 74 69 63 73 20 | 6f 66 20 74 72 65 65 20 |thetics |of tree |
|00001c30| 64 72 61 77 69 6e 67 20 | 61 6e 64 20 74 68 65 20 |drawing |and the |
|00001c40| 61 6c 67 6f 72 69 74 68 | 6d 20 6f 66 0a 52 65 69 |algorith|m of.Rei|
|00001c50| 6e 67 6f 6c 64 20 61 6e | 64 20 54 69 6c 66 6f 72 |ngold an|d Tilfor|
|00001c60| 64 7e 5c 63 69 74 65 7b | 54 69 64 69 65 72 54 72 |d~\cite{|TidierTr|
|00001c70| 65 65 73 7d 2e 20 49 6e | 20 53 65 63 74 69 6f 6e |ees}. In| Section|
|00001c80| 73 7e 35 2c 20 36 2c 20 | 61 6e 64 7e 37 2c 20 77 |s~5, 6, |and~7, w|
|00001c90| 65 0a 64 65 73 63 72 69 | 62 65 20 6f 75 72 20 6d |e.descri|be our m|
|00001ca0| 65 74 68 6f 64 20 6f 66 | 20 69 6e 63 6f 72 70 6f |ethod of| incorpo|
|00001cb0| 72 61 74 69 6e 67 20 74 | 72 65 65 20 64 72 61 77 |rating t|ree draw|
|00001cc0| 69 6e 67 20 69 6e 74 6f | 20 5c 54 65 58 7b 7d 2e |ing into| \TeX{}.|
|00001cd0| 20 54 68 65 6e 2c 0a 69 | 6e 20 74 68 65 20 6c 61 | Then,.i|n the la|
|00001ce0| 73 74 20 74 68 72 65 65 | 20 73 68 6f 72 74 20 73 |st three| short s|
|00001cf0| 65 63 74 69 6f 6e 73 2c | 20 77 65 20 63 6f 6e 73 |ections,| we cons|
|00001d00| 69 64 65 72 20 74 68 65 | 20 65 78 70 65 63 74 65 |ider the| expecte|
|00001d10| 64 20 6e 75 6d 62 65 72 | 20 6f 66 0a 72 65 67 69 |d number| of.regi|
|00001d20| 73 74 65 72 73 20 5c 54 | 65 58 7b 7d 20 6e 65 65 |sters \T|eX{} nee|
|00001d30| 64 73 20 74 6f 20 64 72 | 61 77 20 61 20 74 72 65 |ds to dr|aw a tre|
|00001d40| 65 2c 20 74 68 65 20 75 | 73 65 72 20 69 6e 74 65 |e, the u|ser inte|
|00001d50| 72 66 61 63 65 20 28 61 | 6e 64 20 74 68 72 65 65 |rface (a|nd three|
|00001d60| 0a 5c 54 72 65 65 54 65 | 58 7b 7d 20 65 78 61 6d |.\TreeTe|X{} exam|
|00001d70| 70 6c 65 73 29 2c 20 61 | 6e 64 20 64 69 73 63 75 |ples), a|nd discu|
|00001d80| 73 73 69 6f 6e 20 6f 66 | 2c 20 61 6d 6f 6e 67 20 |ssion of|, among |
|00001d90| 6f 74 68 65 72 20 74 68 | 69 6e 67 73 2c 20 74 68 |other th|ings, th|
|00001da0| 65 0a 70 65 72 66 6f 72 | 6d 61 6e 63 65 20 20 6f |e.perfor|mance  o|
|00001db0| 66 20 5c 54 72 65 65 54 | 65 58 7b 7d 2e 0a 0a 5c |f \TreeT|eX{}...\|
|00001dc0| 73 65 63 74 69 6f 6e 7b | 41 65 73 74 68 65 74 69 |section{|Aestheti|
|00001dd0| 63 61 6c 20 63 72 69 74 | 65 72 69 61 20 66 6f 72 |cal crit|eria for|
|00001de0| 20 64 72 61 77 69 6e 67 | 20 74 72 65 65 73 7d 0a | drawing| trees}.|
|00001df0| 0a 49 6e 20 74 68 69 73 | 20 70 61 70 65 72 2c 20 |.In this| paper, |
|00001e00| 77 65 20 61 72 65 20 64 | 65 61 6c 69 6e 67 20 77 |we are d|ealing w|
|00001e10| 69 74 68 20 6f 72 64 65 | 72 65 64 0a 74 72 65 65 |ith orde|red.tree|
|00001e20| 73 20 69 6e 20 74 68 65 | 20 73 65 6e 73 65 20 6f |s in the| sense o|
|00001e30| 66 7e 5c 63 69 74 65 7b | 41 43 50 7d 2c 20 73 70 |f~\cite{|ACP}, sp|
|00001e40| 65 63 69 66 69 63 61 6c | 6c 79 20 62 69 6e 61 72 |ecifical|ly binar|
|00001e50| 79 20 61 6e 64 20 75 6e | 61 72 79 2d 62 69 6e 61 |y and un|ary-bina|
|00001e60| 72 79 0a 74 72 65 65 73 | 2e 20 41 20 7b 5c 65 6d |ry.trees|. A {\em|
|00001e70| 20 62 69 6e 61 72 79 20 | 74 72 65 65 5c 2f 7d 20 | binary |tree\/} |
|00001e80| 69 73 20 61 20 66 69 6e | 69 74 65 20 73 65 74 20 |is a fin|ite set |
|00001e90| 6f 66 20 6e 6f 64 65 73 | 20 74 68 61 74 20 65 69 |of nodes| that ei|
|00001ea0| 74 68 65 72 0a 69 73 20 | 65 6d 70 74 79 2c 20 6f |ther.is |empty, o|
|00001eb0| 72 20 63 6f 6e 73 69 73 | 74 73 20 6f 66 20 61 20 |r consis|ts of a |
|00001ec0| 72 6f 6f 74 20 61 6e 64 | 20 74 77 6f 20 64 69 73 |root and| two dis|
|00001ed0| 6a 6f 69 6e 74 20 62 69 | 6e 61 72 79 20 74 72 65 |joint bi|nary tre|
|00001ee0| 65 73 20 63 61 6c 6c 65 | 64 0a 74 68 65 20 6c 65 |es calle|d.the le|
|00001ef0| 66 74 20 61 6e 64 20 72 | 69 67 68 74 20 73 75 62 |ft and r|ight sub|
|00001f00| 74 72 65 65 73 20 6f 66 | 20 74 68 65 20 72 6f 6f |trees of| the roo|
|00001f10| 74 2e 20 41 20 7b 5c 65 | 6d 20 75 6e 61 72 79 2d |t. A {\e|m unary-|
|00001f20| 62 69 6e 61 72 79 20 74 | 72 65 65 5c 2f 7d 20 69 |binary t|ree\/} i|
|00001f30| 73 0a 61 20 66 69 6e 69 | 74 65 20 73 65 74 20 6f |s.a fini|te set o|
|00001f40| 66 20 6e 6f 64 65 73 20 | 74 68 61 74 20 65 69 74 |f nodes |that eit|
|00001f50| 68 65 72 20 69 73 20 65 | 6d 70 74 79 2c 20 6f 72 |her is e|mpty, or|
|00001f60| 20 63 6f 6e 73 69 73 74 | 73 20 6f 66 20 61 20 72 | consist|s of a r|
|00001f70| 6f 6f 74 20 61 6e 64 0a | 74 77 6f 20 64 69 73 6a |oot and.|two disj|
|00001f80| 6f 69 6e 74 20 75 6e 61 | 72 79 2d 62 69 6e 61 72 |oint una|ry-binar|
|00001f90| 79 20 74 72 65 65 73 2c | 20 6f 72 20 63 6f 6e 73 |y trees,| or cons|
|00001fa0| 69 73 74 73 20 6f 66 20 | 61 20 72 6f 6f 74 20 61 |ists of |a root a|
|00001fb0| 6e 64 20 6f 6e 65 0a 6e | 6f 6e 65 6d 70 74 79 20 |nd one.n|onempty |
|00001fc0| 75 6e 61 72 79 2d 62 69 | 6e 61 72 79 20 74 72 65 |unary-bi|nary tre|
|00001fd0| 65 2e 20 41 6e 20 7b 5c | 65 6d 20 65 78 74 65 6e |e. An {\|em exten|
|00001fe0| 64 65 64 20 62 69 6e 61 | 72 79 20 74 72 65 65 5c |ded bina|ry tree\|
|00001ff0| 2f 7d 20 69 73 20 61 20 | 62 69 6e 61 72 79 20 74 |/} is a |binary t|
|00002000| 72 65 65 0a 69 6e 20 77 | 68 69 63 68 20 65 61 63 |ree.in w|hich eac|
|00002010| 68 20 6e 6f 64 65 20 68 | 61 73 20 65 69 74 68 65 |h node h|as eithe|
|00002020| 72 20 74 77 6f 20 6e 6f | 6e 65 6d 70 74 79 20 73 |r two no|nempty s|
|00002030| 75 62 74 72 65 65 73 20 | 6f 72 20 74 77 6f 0a 65 |ubtrees |or two.e|
|00002040| 6d 70 74 79 20 73 75 62 | 74 72 65 65 73 2e 0a 0a |mpty sub|trees...|
|00002050| 54 68 65 72 65 20 61 72 | 65 20 73 6f 6d 65 20 62 |There ar|e some b|
|00002060| 61 73 69 63 20 61 67 72 | 65 65 6d 65 6e 74 73 20 |asic agr|eements |
|00002070| 6f 6e 20 68 6f 77 20 73 | 75 63 68 20 74 72 65 65 |on how s|uch tree|
|00002080| 73 20 73 68 6f 75 6c 64 | 20 62 65 20 64 72 61 77 |s should| be draw|
|00002090| 6e 2c 20 72 65 66 6c 65 | 63 74 69 6e 67 0a 74 68 |n, refle|cting.th|
|000020a0| 65 20 74 6f 70 2d 64 6f | 77 6e 20 61 6e 64 20 6c |e top-do|wn and l|
|000020b0| 65 66 74 2d 72 69 67 68 | 74 20 6f 72 64 65 72 69 |eft-righ|t orderi|
|000020c0| 6e 67 20 6f 66 20 6e 6f | 64 65 73 20 69 6e 20 61 |ng of no|des in a|
|000020d0| 20 74 72 65 65 2e 0a 49 | 6e 20 5c 63 69 74 65 7b | tree..I|n \cite{|
|000020e0| 54 69 64 69 65 72 54 72 | 65 65 73 7d 20 61 6e 64 |TidierTr|ees} and|
|000020f0| 20 5c 63 69 74 65 7b 54 | 69 64 79 54 72 65 65 73 | \cite{T|idyTrees|
|00002100| 7d 20 74 68 65 73 65 20 | 62 61 73 69 63 20 61 67 |} these |basic ag|
|00002110| 72 65 65 6d 65 6e 74 73 | 20 77 65 72 65 0a 66 6f |reements| were.fo|
|00002120| 72 6d 61 6c 69 7a 65 64 | 20 61 73 20 74 68 65 20 |rmalized| as the |
|00002130| 66 6f 6c 6c 6f 77 69 6e | 67 20 61 78 69 6f 6d 73 |followin|g axioms|
|00002140| 2e 0a 0a 5c 62 65 67 69 | 6e 7b 65 6e 75 6d 65 72 |...\begi|n{enumer|
|00002150| 61 74 65 7d 0a 5c 69 74 | 65 6d 5b 31 2e 5d 20 54 |ate}.\it|em[1.] T|
|00002160| 72 65 65 73 20 69 6d 70 | 6f 73 65 20 61 20 64 69 |rees imp|ose a di|
|00002170| 73 74 61 6e 63 65 20 6f | 6e 20 74 68 65 20 6e 6f |stance o|n the no|
|00002180| 64 65 73 3b 20 6e 6f 20 | 6e 6f 64 65 0a 20 20 20 |des; no |node.   |
|00002190| 20 20 20 20 20 20 20 73 | 68 6f 75 6c 64 20 62 65 |       s|hould be|
|000021a0| 20 63 6c 6f 73 65 72 20 | 74 6f 20 74 68 65 20 72 | closer |to the r|
|000021b0| 6f 6f 74 20 74 68 61 6e | 20 61 6e 79 20 6f 66 20 |oot than| any of |
|000021c0| 69 74 73 0a 20 20 20 20 | 20 20 20 20 20 20 61 6e |its.    |      an|
|000021d0| 63 65 73 74 6f 72 73 2e | 0a 5c 69 74 65 6d 5b 32 |cestors.|.\item[2|
|000021e0| 2e 5d 20 4e 6f 64 65 73 | 20 6f 6e 20 74 68 65 20 |.] Nodes| on the |
|000021f0| 73 61 6d 65 20 6c 65 76 | 65 6c 20 73 68 6f 75 6c |same lev|el shoul|
|00002200| 64 20 6c 69 65 20 6f 6e | 20 61 20 73 74 72 61 69 |d lie on| a strai|
|00002210| 67 68 74 0a 20 20 20 20 | 20 20 20 20 20 20 6c 69 |ght.    |      li|
|00002220| 6e 65 2c 20 61 6e 64 20 | 74 68 65 20 73 74 72 61 |ne, and |the stra|
|00002230| 69 67 68 74 20 6c 69 6e | 65 73 20 64 65 66 69 6e |ight lin|es defin|
|00002240| 69 6e 67 20 74 68 65 20 | 6c 65 76 65 6c 73 20 73 |ing the |levels s|
|00002250| 68 6f 75 6c 64 20 62 65 | 0a 20 20 20 20 20 20 20 |hould be|.       |
|00002260| 20 20 20 70 61 72 61 6c | 6c 65 6c 2e 0a 5c 69 74 |   paral|lel..\it|
|00002270| 65 6d 5b 33 2e 5d 20 54 | 68 65 20 72 65 6c 61 74 |em[3.] T|he relat|
|00002280| 69 76 65 20 6f 72 64 65 | 72 20 6f 66 20 6e 6f 64 |ive orde|r of nod|
|00002290| 65 73 20 6f 6e 20 61 6e | 79 20 6c 65 76 65 6c 20 |es on an|y level |
|000022a0| 73 68 6f 75 6c 64 20 62 | 65 20 74 68 65 20 73 61 |should b|e the sa|
|000022b0| 6d 65 0a 20 20 20 20 20 | 20 20 20 20 20 61 73 20 |me.     |     as |
|000022c0| 69 6e 20 74 68 65 20 6c | 65 76 65 6c 20 6f 72 64 |in the l|evel ord|
|000022d0| 65 72 20 74 72 61 76 65 | 72 73 61 6c 20 6f 66 20 |er trave|rsal of |
|000022e0| 74 68 65 20 74 72 65 65 | 2e 0a 5c 65 6e 64 7b 65 |the tree|..\end{e|
|000022f0| 6e 75 6d 65 72 61 74 65 | 7d 0a 0a 54 68 65 73 65 |numerate|}..These|
|00002300| 20 61 78 69 6f 6d 73 20 | 67 75 61 72 61 6e 74 65 | axioms |guarante|
|00002310| 65 20 74 68 61 74 20 74 | 72 65 65 73 20 61 72 65 |e that t|rees are|
|00002320| 20 64 72 61 77 6e 20 61 | 73 20 70 6c 61 6e 61 72 | drawn a|s planar|
|00002330| 20 67 72 61 70 68 73 3a | 20 65 64 67 65 73 20 64 | graphs:| edges d|
|00002340| 6f 0a 6e 6f 74 20 69 6e | 74 65 72 73 65 63 74 20 |o.not in|tersect |
|00002350| 65 78 63 65 70 74 20 61 | 74 20 6e 6f 64 65 73 2e |except a|t nodes.|
|00002360| 20 54 77 6f 20 66 75 72 | 74 68 65 72 20 61 78 69 | Two fur|ther axi|
|00002370| 6f 6d 73 20 69 6d 70 72 | 6f 76 65 20 74 68 65 20 |oms impr|ove the |
|00002380| 61 65 73 74 68 65 74 69 | 63 61 6c 0a 61 70 70 65 |aestheti|cal.appe|
|00002390| 61 72 61 6e 63 65 20 6f | 66 20 74 72 65 65 73 2e |arance o|f trees.|
|000023a0| 0a 0a 5c 62 65 67 69 6e | 7b 65 6e 75 6d 65 72 61 |..\begin|{enumera|
|000023b0| 74 65 7d 0a 5c 69 74 65 | 6d 5b 34 2e 5d 20 49 6e |te}.\ite|m[4.] In|
|000023c0| 20 61 20 75 6e 61 72 79 | 2d 62 69 6e 61 72 79 20 | a unary|-binary |
|000023d0| 74 72 65 65 2c 20 65 61 | 63 68 20 6c 65 66 74 20 |tree, ea|ch left |
|000023e0| 63 68 69 6c 64 20 73 68 | 6f 75 6c 64 20 62 65 20 |child sh|ould be |
|000023f0| 70 6f 73 69 74 69 6f 6e | 65 64 0a 20 20 20 20 20 |position|ed.     |
|00002400| 20 20 20 20 20 74 6f 20 | 74 68 65 20 6c 65 66 74 |     to |the left|
|00002410| 20 6f 66 20 69 74 73 20 | 70 61 72 65 6e 74 2c 20 | of its |parent, |
|00002420| 65 61 63 68 0a 20 20 20 | 20 20 20 20 20 20 20 72 |each.   |       r|
|00002430| 69 67 68 74 20 63 68 69 | 6c 64 20 74 6f 20 74 68 |ight chi|ld to th|
|00002440| 65 20 72 69 67 68 74 20 | 6f 66 20 69 74 73 20 70 |e right |of its p|
|00002450| 61 72 65 6e 74 2c 20 61 | 6e 64 20 65 61 63 68 20 |arent, a|nd each |
|00002460| 75 6e 61 72 79 20 63 68 | 69 6c 64 0a 20 20 20 20 |unary ch|ild.    |
|00002470| 20 20 20 20 20 20 73 68 | 6f 75 6c 64 20 62 65 20 |      sh|ould be |
|00002480| 70 6f 73 69 74 69 6f 6e | 65 64 20 62 65 6c 6f 77 |position|ed below|
|00002490| 20 69 74 73 20 70 61 72 | 65 6e 74 2e 0a 5c 69 74 | its par|ent..\it|
|000024a0| 65 6d 5b 35 2e 5d 20 41 | 20 70 61 72 65 6e 74 20 |em[5.] A| parent |
|000024b0| 73 68 6f 75 6c 64 20 62 | 65 20 63 65 6e 74 65 72 |should b|e center|
|000024c0| 65 64 20 6f 76 65 72 20 | 69 74 73 20 63 68 69 6c |ed over |its chil|
|000024d0| 64 72 65 6e 2e 0a 5c 65 | 6e 64 7b 65 6e 75 6d 65 |dren..\e|nd{enume|
|000024e0| 72 61 74 65 7d 0a 0a 41 | 6e 20 61 64 64 69 74 69 |rate}..A|n additi|
|000024f0| 6f 6e 61 6c 20 61 78 69 | 6f 6d 20 64 65 61 6c 73 |onal axi|om deals|
|00002500| 20 77 69 74 68 20 74 68 | 65 20 70 72 6f 62 6c 65 | with th|e proble|
|00002510| 6d 20 6f 66 20 74 72 65 | 65 20 64 72 61 77 69 6e |m of tre|e drawin|
|00002520| 67 73 20 62 65 63 6f 6d | 69 6e 67 20 74 6f 6f 20 |gs becom|ing too |
|00002530| 77 69 64 65 0a 61 6e 64 | 20 74 68 65 72 65 66 6f |wide.and| therefo|
|00002540| 72 65 20 65 78 63 65 65 | 64 69 6e 67 20 74 68 65 |re excee|ding the|
|00002550| 20 70 68 79 73 69 63 61 | 6c 20 6c 69 6d 69 74 20 | physica|l limit |
|00002560| 6f 66 20 74 68 65 20 6f | 75 74 70 75 74 20 6d 65 |of the o|utput me|
|00002570| 64 69 75 6d 3a 0a 0a 5c | 62 65 67 69 6e 7b 65 6e |dium:..\|begin{en|
|00002580| 75 6d 65 72 61 74 65 7d | 0a 5c 69 74 65 6d 5b 36 |umerate}|.\item[6|
|00002590| 2e 5d 20 54 72 65 65 20 | 64 72 61 77 69 6e 67 73 |.] Tree |drawings|
|000025a0| 20 73 68 6f 75 6c 64 20 | 6f 63 63 75 70 79 20 61 | should |occupy a|
|000025b0| 73 20 6c 69 74 74 6c 65 | 20 77 69 64 74 68 20 61 |s little| width a|
|000025c0| 73 20 70 6f 73 73 69 62 | 6c 65 20 77 69 74 68 6f |s possib|le witho|
|000025d0| 75 74 0a 20 20 20 20 20 | 20 20 20 20 20 76 69 6f |ut.     |     vio|
|000025e0| 6c 61 74 69 6e 67 20 74 | 68 65 20 6f 74 68 65 72 |lating t|he other|
|000025f0| 20 61 78 69 6f 6d 73 2e | 0a 5c 65 6e 64 7b 65 6e | axioms.|.\end{en|
|00002600| 75 6d 65 72 61 74 65 7d | 0a 0a 49 6e 20 5c 63 69 |umerate}|..In \ci|
|00002610| 74 65 7b 54 69 64 79 54 | 72 65 65 73 7d 2c 20 57 |te{TidyT|rees}, W|
|00002620| 65 74 68 65 72 65 6c 6c | 20 61 6e 64 20 53 68 61 |etherell| and Sha|
|00002630| 6e 6e 6f 6e 20 69 6e 74 | 72 6f 64 75 63 65 20 74 |nnon int|roduce t|
|00002640| 77 6f 20 61 6c 67 6f 72 | 69 74 68 6d 73 20 66 6f |wo algor|ithms fo|
|00002650| 72 0a 74 72 65 65 20 64 | 72 61 77 69 6e 67 73 2c |r.tree d|rawings,|
|00002660| 20 74 68 65 20 66 69 72 | 73 74 20 6f 66 20 77 68 | the fir|st of wh|
|00002670| 69 63 68 20 66 75 6c 66 | 69 6c 6c 73 20 61 78 69 |ich fulf|ills axi|
|00002680| 6f 6d 73 7e 31 2d 2d 35 | 2c 20 61 6e 64 20 74 68 |oms~1--5|, and th|
|00002690| 65 20 73 65 63 6f 6e 64 | 0a 31 2d 2d 36 2e 20 48 |e second|.1--6. H|
|000026a0| 6f 77 65 76 65 72 2c 20 | 61 73 20 52 65 69 6e 67 |owever, |as Reing|
|000026b0| 6f 6c 64 20 61 6e 64 20 | 54 69 6c 66 6f 72 64 20 |old and |Tilford |
|000026c0| 69 6e 20 5c 63 69 74 65 | 7b 54 69 64 69 65 72 54 |in \cite|{TidierT|
|000026d0| 72 65 65 73 7d 0a 70 6f | 69 6e 74 20 6f 75 74 2c |rees}.po|int out,|
|000026e0| 20 74 68 65 72 65 20 69 | 73 20 61 20 6c 61 63 6b | there i|s a lack|
|000026f0| 20 6f 66 20 73 79 6d 6d | 65 74 72 79 20 69 6e 20 | of symm|etry in |
|00002700| 74 68 65 20 61 6c 67 6f | 72 69 74 68 6d 73 20 6f |the algo|rithms o|
|00002710| 66 0a 57 65 74 68 65 72 | 65 6c 6c 20 61 6e 64 20 |f.Wether|ell and |
|00002720| 53 68 61 6e 6e 6f 6e 20 | 77 68 69 63 68 20 6d 61 |Shannon |which ma|
|00002730| 79 20 6c 65 61 64 20 74 | 6f 20 75 6e 70 6c 65 61 |y lead t|o unplea|
|00002740| 73 61 6e 74 20 72 65 73 | 75 6c 74 73 3b 0a 74 68 |sant res|ults;.th|
|00002750| 65 72 65 66 6f 72 65 2c | 20 52 65 69 6e 67 6f 6c |erefore,| Reingol|
|00002760| 64 20 61 6e 64 20 54 69 | 6c 66 6f 72 64 20 69 6e |d and Ti|lford in|
|00002770| 74 72 6f 64 75 63 65 20 | 61 20 6e 65 77 20 73 74 |troduce |a new st|
|00002780| 72 75 63 74 75 72 65 64 | 0a 61 78 69 6f 6d 2e 0a |ructured|.axiom..|
|00002790| 0a 5c 62 65 67 69 6e 7b | 65 6e 75 6d 65 72 61 74 |.\begin{|enumerat|
|000027a0| 65 7d 0a 5c 69 74 65 6d | 5b 37 2e 5d 20 41 20 73 |e}.\item|[7.] A s|
|000027b0| 75 62 74 72 65 65 20 6f | 66 20 61 20 67 69 76 65 |ubtree o|f a give|
|000027c0| 6e 20 74 72 65 65 20 73 | 68 6f 75 6c 64 20 62 65 |n tree s|hould be|
|000027d0| 0a 20 20 20 20 20 20 20 | 20 20 20 64 72 61 77 6e |.       |   drawn|
|000027e0| 20 74 68 65 20 73 61 6d | 65 20 77 61 79 20 72 65 | the sam|e way re|
|000027f0| 67 61 72 64 6c 65 73 73 | 20 6f 66 20 77 68 65 72 |gardless| of wher|
|00002800| 65 20 69 74 20 6f 63 63 | 75 72 73 20 69 6e 20 74 |e it occ|urs in t|
|00002810| 68 65 20 74 72 65 65 2e | 0a 5c 65 6e 64 7b 65 6e |he tree.|.\end{en|
|00002820| 75 6d 65 72 61 74 65 7d | 0a 0a 41 78 69 6f 6d 7e |umerate}|..Axiom~|
|00002830| 37 20 61 6c 6c 6f 77 73 | 20 74 68 65 20 73 61 6d |7 allows| the sam|
|00002840| 65 20 74 72 65 65 20 74 | 6f 20 62 65 20 64 72 61 |e tree t|o be dra|
|00002850| 77 6e 20 64 69 66 66 65 | 72 65 6e 74 6c 79 20 6f |wn diffe|rently o|
|00002860| 6e 6c 79 20 77 68 65 6e | 20 69 74 20 6f 63 63 75 |nly when| it occu|
|00002870| 72 73 20 61 73 0a 61 20 | 73 75 62 74 72 65 65 20 |rs as.a |subtree |
|00002880| 69 6e 20 64 69 66 66 65 | 72 65 6e 74 20 74 72 65 |in diffe|rent tre|
|00002890| 65 73 2e 0a 52 65 69 6e | 67 6f 6c 64 20 61 6e 64 |es..Rein|gold and|
|000028a0| 20 54 69 6c 66 6f 72 64 | 20 67 69 76 65 20 61 6e | Tilford| give an|
|000028b0| 20 61 6c 67 6f 72 69 74 | 68 6d 20 77 68 69 63 68 | algorit|hm which|
|000028c0| 20 66 75 6c 66 69 6c 6c | 73 20 61 78 69 6f 6d 73 | fulfill|s axioms|
|000028d0| 7e 31 2d 2d 35 0a 61 6e | 64 7e 37 2e 20 41 6c 74 |~1--5.an|d~7. Alt|
|000028e0| 68 6f 75 67 68 0a 74 68 | 69 73 20 61 6c 67 6f 72 |hough.th|is algor|
|000028f0| 69 74 68 6d 20 64 6f 65 | 73 6e 27 74 20 66 75 6c |ithm doe|sn't ful|
|00002900| 66 69 6c 6c 20 61 78 69 | 6f 6d 7e 36 2c 0a 74 68 |fill axi|om~6,.th|
|00002910| 65 20 61 65 73 74 68 65 | 74 69 63 61 6c 20 69 6d |e aesthe|tical im|
|00002920| 70 72 6f 76 65 6d 65 6e | 74 73 20 61 72 65 20 77 |provemen|ts are w|
|00002930| 65 6c 6c 20 77 6f 72 74 | 68 20 74 68 65 20 61 64 |ell wort|h the ad|
|00002940| 64 69 74 69 6f 6e 61 6c | 20 73 70 61 63 65 2e 0a |ditional| space..|
|00002950| 5c 66 69 67 7b 61 6c 67 | 6f 72 69 74 68 6d 73 7d |\fig{alg|orithms}|
|00002960| 20 69 6c 6c 75 73 74 72 | 61 74 65 73 20 74 68 65 | illustr|ates the|
|00002970| 20 62 65 6e 65 66 69 74 | 73 20 6f 66 20 61 78 69 | benefit|s of axi|
|00002980| 6f 6d 7e 37 2c 20 61 6e | 64 20 5c 66 69 67 7b 6e |om~7, an|d \fig{n|
|00002990| 61 72 72 6f 77 74 72 65 | 65 73 7d 0a 73 68 6f 77 |arrowtre|es}.show|
|000029a0| 73 20 74 68 61 74 20 74 | 68 65 20 61 6c 67 6f 72 |s that t|he algor|
|000029b0| 69 74 68 6d 20 6f 66 20 | 52 65 69 6e 67 6f 6c 64 |ithm of |Reingold|
|000029c0| 20 61 6e 64 20 54 69 6c | 66 6f 72 64 20 76 69 6f | and Til|ford vio|
|000029d0| 6c 61 74 65 73 20 61 78 | 69 6f 6d 7e 36 2e 0a 0a |lates ax|iom~6...|
|000029e0| 5c 62 65 67 69 6e 7b 46 | 69 67 75 72 65 7d 0a 5c |\begin{F|igure}.\|
|000029f0| 63 65 6e 74 65 72 69 6e | 67 0a 5c 6c 65 61 76 65 |centerin|g.\leave|
|00002a00| 76 6d 6f 64 65 5c 6e 6f | 69 6e 64 65 6e 74 0a 5c |vmode\no|indent.\|
|00002a10| 62 65 67 69 6e 7b 54 72 | 65 65 7d 0a 5c 65 6e 6f |begin{Tr|ee}.\eno|
|00002a20| 64 65 0a 5c 65 6e 6f 64 | 65 5c 65 6e 6f 64 65 5c |de.\enod|e\enode\|
|00002a30| 69 6e 6f 64 65 5c 65 6e | 6f 64 65 5c 65 6e 6f 64 |inode\en|ode\enod|
|00002a40| 65 5c 69 6e 6f 64 65 5c | 69 6e 6f 64 65 5c 69 6e |e\inode\|inode\in|
|00002a50| 6f 64 65 0a 5c 6e 6f 64 | 65 7b 5c 65 78 74 65 72 |ode.\nod|e{\exter|
|00002a60| 6e 61 6c 5c 74 79 70 65 | 7b 64 6f 74 7d 5c 72 67 |nal\type|{dot}\rg|
|00002a70| 68 74 7b 5c 75 6e 73 6b | 69 70 5c 68 73 6b 69 70 |ht{\unsk|ip\hskip|
|00002a80| 32 5c 6d 69 6e 73 40 70 | 5c 68 73 6b 69 70 32 5c |2\mins@p|\hskip2\|
|00002a90| 64 6f 74 77 40 64 74 68 | 7d 7d 0a 5c 65 6e 6f 64 |dotw@dth|}}.\enod|
|00002aa0| 65 5c 65 6e 6f 64 65 5c | 69 6e 6f 64 65 5c 65 6e |e\enode\|inode\en|
|00002ab0| 6f 64 65 5c 65 6e 6f 64 | 65 5c 69 6e 6f 64 65 5c |ode\enod|e\inode\|
|00002ac0| 69 6e 6f 64 65 5c 69 6e | 6f 64 65 0a 5c 69 6e 6f |inode\in|ode.\ino|
|00002ad0| 64 65 0a 5c 65 6e 64 7b | 54 72 65 65 7d 0a 5c 68 |de.\end{|Tree}.\h|
|00002ae0| 73 6b 69 70 5c 6c 65 66 | 74 64 69 73 74 5c 62 6f |skip\lef|tdist\bo|
|00002af0| 78 5c 54 65 58 54 72 65 | 65 5c 68 73 6b 69 70 5c |x\TeXTre|e\hskip\|
|00002b00| 72 69 67 68 74 64 69 73 | 74 5c 71 71 75 61 64 0a |rightdis|t\qquad.|
|00002b10| 5c 62 65 67 69 6e 7b 54 | 72 65 65 7d 0a 5c 65 6e |\begin{T|ree}.\en|
|00002b20| 6f 64 65 0a 5c 65 6e 6f | 64 65 5c 65 6e 6f 64 65 |ode.\eno|de\enode|
|00002b30| 5c 69 6e 6f 64 65 5c 65 | 6e 6f 64 65 5c 65 6e 6f |\inode\e|node\eno|
|00002b40| 64 65 5c 69 6e 6f 64 65 | 5c 69 6e 6f 64 65 5c 69 |de\inode|\inode\i|
|00002b50| 6e 6f 64 65 0a 5c 65 6e | 6f 64 65 0a 5c 65 6e 6f |node.\en|ode.\eno|
|00002b60| 64 65 5c 65 6e 6f 64 65 | 5c 69 6e 6f 64 65 5c 65 |de\enode|\inode\e|
|00002b70| 6e 6f 64 65 5c 65 6e 6f | 64 65 5c 69 6e 6f 64 65 |node\eno|de\inode|
|00002b80| 5c 69 6e 6f 64 65 5c 69 | 6e 6f 64 65 0a 5c 69 6e |\inode\i|node.\in|
|00002b90| 6f 64 65 0a 5c 65 6e 64 | 7b 54 72 65 65 7d 0a 5c |ode.\end|{Tree}.\|
|00002ba0| 68 73 6b 69 70 5c 6c 65 | 66 74 64 69 73 74 5c 62 |hskip\le|ftdist\b|
|00002bb0| 6f 78 5c 54 65 58 54 72 | 65 65 5c 68 73 6b 69 70 |ox\TeXTr|ee\hskip|
|00002bc0| 5c 72 69 67 68 74 64 69 | 73 74 5c 0a 5c 63 61 70 |\rightdi|st\.\cap|
|00002bd0| 74 69 6f 6e 7b 54 68 65 | 20 6c 65 66 74 20 74 72 |tion{The| left tr|
|00002be0| 65 65 20 69 73 20 64 72 | 61 77 6e 20 62 79 20 74 |ee is dr|awn by t|
|00002bf0| 68 65 20 61 6c 67 6f 72 | 69 74 68 6d 20 6f 66 20 |he algor|ithm of |
|00002c00| 57 65 74 68 65 72 65 6c | 6c 20 61 6e 64 20 53 68 |Wetherel|l and Sh|
|00002c10| 61 6e 6e 6f 6e 2c 0a 61 | 6e 64 20 74 68 65 20 74 |annon,.a|nd the t|
|00002c20| 69 64 69 65 72 20 72 69 | 67 68 74 20 6f 6e 65 20 |idier ri|ght one |
|00002c30| 69 73 20 64 72 61 77 6e | 20 62 79 20 74 68 65 20 |is drawn| by the |
|00002c40| 61 6c 67 6f 72 69 74 68 | 6d 20 6f 66 20 52 65 69 |algorith|m of Rei|
|00002c50| 6e 67 6f 6c 64 20 61 6e | 64 20 54 69 6c 66 6f 72 |ngold an|d Tilfor|
|00002c60| 64 2e 7d 0a 5c 6c 61 62 | 65 6c 7b 61 6c 67 6f 72 |d.}.\lab|el{algor|
|00002c70| 69 74 68 6d 73 7d 0a 0a | 5c 76 73 70 61 63 65 7b |ithms}..|\vspace{|
|00002c80| 5c 66 69 67 73 70 61 63 | 65 7d 0a 5c 63 65 6e 74 |\figspac|e}.\cent|
|00002c90| 65 72 69 6e 67 0a 5c 6c | 65 61 76 65 76 6d 6f 64 |ering.\l|eavevmod|
|00002ca0| 65 5c 6e 6f 69 6e 64 65 | 6e 74 0a 5c 62 65 67 69 |e\noinde|nt.\begi|
|00002cb0| 6e 7b 54 72 65 65 7d 0a | 5c 65 6e 6f 64 65 5c 65 |n{Tree}.|\enode\e|
|00002cc0| 6e 6f 64 65 5c 65 6e 6f | 64 65 5c 65 6e 6f 64 65 |node\eno|de\enode|
|00002cd0| 5c 65 6e 6f 64 65 5c 65 | 6e 6f 64 65 5c 65 6e 6f |\enode\e|node\eno|
|00002ce0| 64 65 5c 65 6e 6f 64 65 | 5c 65 6e 6f 64 65 0a 5c |de\enode|\enode.\|
|00002cf0| 65 6e 6f 64 65 5c 69 6e | 6f 64 65 5c 69 6e 6f 64 |enode\in|ode\inod|
|00002d00| 65 5c 69 6e 6f 64 65 0a | 5c 65 6e 6f 64 65 5c 69 |e\inode.|\enode\i|
|00002d10| 6e 6f 64 65 5c 69 6e 6f | 64 65 5c 69 6e 6f 64 65 |node\ino|de\inode|
|00002d20| 0a 5c 65 6e 6f 64 65 5c | 69 6e 6f 64 65 5c 69 6e |.\enode\|inode\in|
|00002d30| 6f 64 65 5c 69 6e 6f 64 | 65 0a 5c 65 6e 6f 64 65 |ode\inod|e.\enode|
|00002d40| 5c 69 6e 6f 64 65 5c 69 | 6e 6f 64 65 5c 69 6e 6f |\inode\i|node\ino|
|00002d50| 64 65 0a 5c 65 6e 64 7b | 54 72 65 65 7d 0a 5c 68 |de.\end{|Tree}.\h|
|00002d60| 73 6b 69 70 5c 6c 65 66 | 74 64 69 73 74 5c 62 6f |skip\lef|tdist\bo|
|00002d70| 78 5c 54 65 58 54 72 65 | 65 5c 68 73 6b 69 70 5c |x\TeXTre|e\hskip\|
|00002d80| 72 69 67 68 74 64 69 73 | 74 5c 71 71 75 61 64 0a |rightdis|t\qquad.|
|00002d90| 5c 62 65 67 69 6e 7b 54 | 72 65 65 7d 0a 5c 65 6e |\begin{T|ree}.\en|
|00002da0| 6f 64 65 5c 65 6e 6f 64 | 65 5c 65 6e 6f 64 65 5c |ode\enod|e\enode\|
|00002db0| 65 6e 6f 64 65 5c 65 6e | 6f 64 65 5c 65 6e 6f 64 |enode\en|ode\enod|
|00002dc0| 65 5c 65 6e 6f 64 65 5c | 65 6e 6f 64 65 0a 5c 6e |e\enode\|enode.\n|
|00002dd0| 6f 64 65 7b 5c 65 78 74 | 65 72 6e 61 6c 5c 74 79 |ode{\ext|ernal\ty|
|00002de0| 70 65 7b 64 6f 74 7d 5c | 72 67 68 74 7b 5c 75 6e |pe{dot}\|rght{\un|
|00002df0| 73 6b 69 70 5c 68 73 6b | 69 70 5c 6d 69 6e 73 40 |skip\hsk|ip\mins@|
|00002e00| 70 5c 68 73 6b 69 70 5c | 64 6f 74 77 40 64 74 68 |p\hskip\|dotw@dth|
|00002e10| 7d 7d 0a 5c 65 6e 6f 64 | 65 5c 69 6e 6f 64 65 5c |}}.\enod|e\inode\|
|00002e20| 69 6e 6f 64 65 5c 6e 6f | 64 65 7b 5c 74 79 70 65 |inode\no|de{\type|
|00002e30| 7b 64 6f 74 7d 5c 72 67 | 68 74 7b 5c 75 6e 73 6b |{dot}\rg|ht{\unsk|
|00002e40| 69 70 5c 68 73 6b 69 70 | 5c 6d 69 6e 73 40 70 5c |ip\hskip|\mins@p\|
|00002e50| 68 73 6b 69 70 5c 64 6f | 74 77 40 64 74 68 7d 7d |hskip\do|tw@dth}}|
|00002e60| 0a 5c 65 6e 6f 64 65 5c | 69 6e 6f 64 65 5c 69 6e |.\enode\|inode\in|
|00002e70| 6f 64 65 5c 6e 6f 64 65 | 7b 5c 74 79 70 65 7b 64 |ode\node|{\type{d|
|00002e80| 6f 74 7d 5c 72 67 68 74 | 7b 5c 75 6e 73 6b 69 70 |ot}\rght|{\unskip|
|00002e90| 5c 68 73 6b 69 70 5c 6d | 69 6e 73 40 70 5c 68 73 |\hskip\m|ins@p\hs|
|00002ea0| 6b 69 70 5c 64 6f 74 77 | 40 64 74 68 7d 7d 0a 5c |kip\dotw|@dth}}.\|
|00002eb0| 65 6e 6f 64 65 5c 69 6e | 6f 64 65 5c 69 6e 6f 64 |enode\in|ode\inod|
|00002ec0| 65 5c 6e 6f 64 65 7b 5c | 74 79 70 65 7b 64 6f 74 |e\node{\|type{dot|
|00002ed0| 7d 5c 72 67 68 74 7b 5c | 75 6e 73 6b 69 70 5c 68 |}\rght{\|unskip\h|
|00002ee0| 73 6b 69 70 5c 6d 69 6e | 73 40 70 5c 68 73 6b 69 |skip\min|s@p\hski|
|00002ef0| 70 5c 64 6f 74 77 40 64 | 74 68 7d 7d 0a 5c 65 6e |p\dotw@d|th}}.\en|
|00002f00| 6f 64 65 5c 69 6e 6f 64 | 65 5c 69 6e 6f 64 65 5c |ode\inod|e\inode\|
|00002f10| 69 6e 6f 64 65 0a 5c 65 | 6e 64 7b 54 72 65 65 7d |inode.\e|nd{Tree}|
|00002f20| 0a 5c 68 73 6b 69 70 5c | 6c 65 66 74 64 69 73 74 |.\hskip\|leftdist|
|00002f30| 5c 62 6f 78 5c 54 65 58 | 54 72 65 65 5c 68 73 6b |\box\TeX|Tree\hsk|
|00002f40| 69 70 5c 72 69 67 68 74 | 64 69 73 74 5c 0a 5c 63 |ip\right|dist\.\c|
|00002f50| 61 70 74 69 6f 6e 7b 54 | 68 65 20 6c 65 66 74 20 |aption{T|he left |
|00002f60| 74 72 65 65 20 69 73 20 | 64 72 61 77 6e 20 62 79 |tree is |drawn by|
|00002f70| 20 74 68 65 20 61 6c 67 | 6f 72 69 74 68 6d 20 6f | the alg|orithm o|
|00002f80| 66 20 52 65 69 6e 67 6f | 6c 64 20 61 6e 64 20 54 |f Reingo|ld and T|
|00002f90| 69 6c 66 6f 72 64 2c 20 | 62 75 74 0a 74 68 65 20 |ilford, |but.the |
|00002fa0| 72 69 67 68 74 20 74 72 | 65 65 20 73 68 6f 77 73 |right tr|ee shows|
|00002fb0| 20 74 68 61 74 20 6e 61 | 72 72 6f 77 65 72 20 64 | that na|rrower d|
|00002fc0| 72 61 77 69 6e 67 73 20 | 66 75 6c 66 69 6c 6c 69 |rawings |fulfilli|
|00002fd0| 6e 67 20 61 6c 6c 20 61 | 65 73 74 68 65 74 69 63 |ng all a|esthetic|
|00002fe0| 20 61 78 69 6f 6d 73 0a | 61 72 65 20 70 6f 73 73 | axioms.|are poss|
|00002ff0| 69 62 6c 65 2e 7d 0a 5c | 6c 61 62 65 6c 7b 6e 61 |ible.}.\|label{na|
|00003000| 72 72 6f 77 74 72 65 65 | 73 7d 0a 5c 65 6e 64 7b |rrowtree|s}.\end{|
|00003010| 46 69 67 75 72 65 7d 0a | 0a 0a 5c 73 65 63 74 69 |Figure}.|..\secti|
|00003020| 6f 6e 7b 54 68 65 20 61 | 6c 67 6f 72 69 74 68 6d |on{The a|lgorithm|
|00003030| 20 6f 66 20 52 65 69 6e | 67 6f 6c 64 20 61 6e 64 | of Rein|gold and|
|00003040| 20 54 69 6c 66 6f 72 64 | 7d 0a 0a 54 68 65 20 61 | Tilford|}..The a|
|00003050| 6c 67 6f 72 69 74 68 6d | 20 6f 66 20 52 65 69 6e |lgorithm| of Rein|
|00003060| 67 6f 6c 64 20 61 6e 64 | 20 54 69 6c 66 6f 72 64 |gold and| Tilford|
|00003070| 20 28 68 65 72 65 61 66 | 74 65 72 20 63 61 6c 6c | (hereaf|ter call|
|00003080| 65 64 20 60 60 74 68 65 | 20 52 54 7e 61 6c 67 6f |ed ``the| RT~algo|
|00003090| 72 69 74 68 6d 27 27 29 | 0a 74 61 6b 65 73 20 61 |rithm'')|.takes a|
|000030a0| 20 6d 6f 64 75 6c 61 72 | 20 61 70 70 72 6f 61 63 | modular| approac|
|000030b0| 68 20 74 6f 20 74 68 65 | 0a 70 6f 73 69 74 69 6f |h to the|.positio|
|000030c0| 6e 69 6e 67 20 6f 66 20 | 6e 6f 64 65 73 2e 20 54 |ning of |nodes. T|
|000030d0| 68 65 20 72 65 6c 61 74 | 69 76 65 20 70 6f 73 69 |he relat|ive posi|
|000030e0| 74 69 6f 6e 73 20 6f 66 | 20 74 68 65 20 6e 6f 64 |tions of| the nod|
|000030f0| 65 73 20 69 6e 20 61 20 | 73 75 62 74 72 65 65 0a |es in a |subtree.|
|00003100| 61 72 65 20 63 61 6c 63 | 75 6c 61 74 65 64 20 69 |are calc|ulated i|
|00003110| 6e 64 65 70 65 6e 64 65 | 6e 74 6c 79 20 6f 66 20 |ndepende|ntly of |
|00003120| 74 68 65 20 72 65 73 74 | 20 6f 66 20 74 68 65 20 |the rest| of the |
|00003130| 74 72 65 65 2e 20 41 66 | 74 65 72 20 74 68 65 0a |tree. Af|ter the.|
|00003140| 72 65 6c 61 74 69 76 65 | 20 70 6f 73 69 74 69 6f |relative| positio|
|00003150| 6e 73 20 6f 66 20 74 77 | 6f 20 73 75 62 74 72 65 |ns of tw|o subtre|
|00003160| 65 73 20 68 61 76 65 20 | 62 65 65 6e 20 63 61 6c |es have |been cal|
|00003170| 63 75 6c 61 74 65 64 2c | 20 74 68 65 79 20 63 61 |culated,| they ca|
|00003180| 6e 20 62 65 0a 6a 6f 69 | 6e 65 64 20 61 73 20 73 |n be.joi|ned as s|
|00003190| 69 62 6c 69 6e 67 73 20 | 69 6e 20 61 20 6c 61 72 |iblings |in a lar|
|000031a0| 67 65 72 20 74 72 65 65 | 20 62 79 20 70 6c 61 63 |ger tree| by plac|
|000031b0| 69 6e 67 20 74 68 65 6d | 20 61 73 20 63 6c 6f 73 |ing them| as clos|
|000031c0| 65 0a 74 6f 67 65 74 68 | 65 72 20 61 73 20 70 6f |e.togeth|er as po|
|000031d0| 73 73 69 62 6c 65 20 61 | 6e 64 20 63 65 6e 74 65 |ssible a|nd cente|
|000031e0| 72 69 6e 67 20 74 68 65 | 20 70 61 72 65 6e 74 20 |ring the| parent |
|000031f0| 6e 6f 64 65 20 61 62 6f | 76 65 20 74 68 65 6d 2e |node abo|ve them.|
|00003200| 0a 49 6e 63 69 64 65 6e | 74 61 6c 6c 79 2c 20 74 |.Inciden|tally, t|
|00003210| 68 69 73 20 6d 6f 64 75 | 6c 61 72 20 61 70 70 72 |his modu|lar appr|
|00003220| 6f 61 63 68 20 69 73 20 | 74 68 65 20 72 65 61 73 |oach is |the reas|
|00003230| 6f 6e 20 74 68 61 74 20 | 74 68 65 0a 61 6c 67 6f |on that |the.algo|
|00003240| 72 69 74 68 6d 20 66 61 | 69 6c 73 20 74 6f 20 66 |rithm fa|ils to f|
|00003250| 75 6c 66 69 6c 6c 20 61 | 78 69 6f 6d 7e 36 3b 20 |ulfill a|xiom~6; |
|00003260| 73 65 65 7e 5c 63 69 74 | 65 7b 43 6f 6d 70 6c 65 |see~\cit|e{Comple|
|00003270| 78 69 74 79 7d 2e 0a 54 | 77 6f 20 73 69 62 6c 69 |xity}..T|wo sibli|
|00003280| 6e 67 20 73 75 62 74 72 | 65 65 73 20 61 72 65 20 |ng subtr|ees are |
|00003290| 70 6c 61 63 65 64 20 61 | 73 20 63 6c 6f 73 65 20 |placed a|s close |
|000032a0| 74 6f 67 65 74 68 65 72 | 20 61 73 20 70 6f 73 73 |together| as poss|
|000032b0| 69 62 6c 65 2c 0a 64 75 | 72 69 6e 67 20 61 20 70 |ible,.du|ring a p|
|000032c0| 6f 73 74 6f 72 64 65 72 | 20 74 72 61 76 65 72 73 |ostorder| travers|
|000032d0| 61 6c 2c 20 61 73 20 66 | 6f 6c 6c 6f 77 73 2e 0a |al, as f|ollows..|
|000032e0| 49 6d 61 67 69 6e 65 20 | 74 68 61 74 20 74 68 65 |Imagine |that the|
|000032f0| 20 74 77 6f 20 73 75 62 | 74 72 65 65 73 20 6f 66 | two sub|trees of|
|00003300| 20 61 20 62 69 6e 61 72 | 79 20 6e 6f 64 65 0a 68 | a binar|y node.h|
|00003310| 61 76 65 20 62 65 65 6e | 20 64 72 61 77 6e 20 61 |ave been| drawn a|
|00003320| 6e 64 20 63 75 74 20 6f | 75 74 20 6f 66 20 70 61 |nd cut o|ut of pa|
|00003330| 70 65 72 20 61 6c 6f 6e | 67 0a 74 68 65 69 72 20 |per alon|g.their |
|00003340| 63 6f 6e 74 6f 75 72 73 | 2e 20 54 68 65 6e 2c 20 |contours|. Then, |
|00003350| 73 74 61 72 74 69 6e 67 | 20 77 69 74 68 20 74 68 |starting| with th|
|00003360| 65 20 74 77 6f 20 73 75 | 62 74 72 65 65 73 20 73 |e two su|btrees s|
|00003370| 75 70 65 72 69 6d 70 6f | 73 65 64 20 61 74 20 74 |uperimpo|sed at t|
|00003380| 68 65 69 72 0a 72 6f 6f | 74 73 2c 20 6d 6f 76 65 |heir.roo|ts, move|
|00003390| 20 74 68 65 6d 20 61 70 | 61 72 74 20 75 6e 74 69 | them ap|art unti|
|000033a0| 6c 20 61 20 6d 69 6e 69 | 6d 61 6c 20 61 67 72 65 |l a mini|mal agre|
|000033b0| 65 64 20 75 70 6f 6e 20 | 64 69 73 74 61 6e 63 65 |ed upon |distance|
|000033c0| 0a 62 65 74 77 65 65 6e | 20 74 68 65 20 74 72 65 |.between| the tre|
|000033d0| 65 73 20 69 73 20 6f 62 | 74 61 69 6e 65 64 20 61 |es is ob|tained a|
|000033e0| 74 20 65 61 63 68 20 6c | 65 76 65 6c 2e 20 54 68 |t each l|evel. Th|
|000033f0| 69 73 20 63 61 6e 20 62 | 65 20 64 6f 6e 65 20 67 |is can b|e done g|
|00003400| 72 61 64 75 61 6c 6c 79 | 2e 0a 49 6e 69 74 69 61 |radually|..Initia|
|00003410| 6c 6c 79 2c 20 74 68 65 | 69 72 20 72 6f 6f 74 73 |lly, the|ir roots|
|00003420| 20 61 72 65 20 73 65 70 | 61 72 61 74 65 64 20 62 | are sep|arated b|
|00003430| 79 20 73 6f 6d 65 20 61 | 67 72 65 65 64 20 75 70 |y some a|greed up|
|00003440| 6f 6e 20 6d 69 6e 69 6d | 75 6d 0a 64 69 73 74 61 |on minim|um.dista|
|00003450| 6e 63 65 3b 20 74 68 65 | 6e 2c 20 61 74 20 74 68 |nce; the|n, at th|
|00003460| 65 20 6e 65 78 74 20 6c | 65 76 65 6c 2c 20 74 68 |e next l|evel, th|
|00003470| 65 79 20 61 72 65 20 70 | 75 73 68 65 64 0a 61 70 |ey are p|ushed.ap|
|00003480| 61 72 74 20 75 6e 74 69 | 6c 20 74 68 65 20 6d 69 |art unti|l the mi|
|00003490| 6e 69 6d 75 6d 20 73 65 | 70 61 72 61 74 69 6f 6e |nimum se|paration|
|000034a0| 20 69 73 20 65 73 74 61 | 62 6c 69 73 68 65 64 20 | is esta|blished |
|000034b0| 74 68 65 72 65 2e 0a 54 | 68 69 73 20 70 72 6f 63 |there..T|his proc|
|000034c0| 65 73 73 20 69 73 20 63 | 6f 6e 74 69 6e 75 65 64 |ess is c|ontinued|
|000034d0| 20 61 74 20 73 75 63 63 | 65 73 73 69 76 65 6c 79 | at succ|essively|
|000034e0| 20 6c 6f 77 65 72 20 6c | 65 76 65 6c 73 20 75 6e | lower l|evels un|
|000034f0| 74 69 6c 20 74 68 65 0a | 6c 61 73 74 20 6c 65 76 |til the.|last lev|
|00003500| 65 6c 20 6f 66 20 74 68 | 65 20 73 68 6f 72 74 65 |el of th|e shorte|
|00003510| 72 20 73 75 62 74 72 65 | 65 20 69 73 20 72 65 61 |r subtre|e is rea|
|00003520| 63 68 65 64 2e 20 41 74 | 20 73 6f 6d 65 20 6c 65 |ched. At| some le|
|00003530| 76 65 6c 73 20 6e 6f 20 | 6d 6f 76 65 6d 65 6e 74 |vels no |movement|
|00003540| 20 6d 61 79 20 62 65 0a | 6e 65 63 65 73 73 61 72 | may be.|necessar|
|00003550| 79 2c 20 62 75 74 20 61 | 74 20 6e 6f 20 6c 65 76 |y, but a|t no lev|
|00003560| 65 6c 20 61 72 65 20 74 | 68 65 20 74 77 6f 20 73 |el are t|he two s|
|00003570| 75 62 74 72 65 65 73 20 | 6d 6f 76 65 64 20 63 6c |ubtrees |moved cl|
|00003580| 6f 73 65 72 0a 74 6f 67 | 65 74 68 65 72 2e 20 57 |oser.tog|ether. W|
|00003590| 68 65 6e 20 74 68 65 20 | 70 72 6f 63 65 73 73 20 |hen the |process |
|000035a0| 69 73 20 63 6f 6d 70 6c | 65 74 65 2c 20 74 68 65 |is compl|ete, the|
|000035b0| 20 70 6f 73 69 74 69 6f | 6e 20 6f 66 20 74 68 65 | positio|n of the|
|000035c0| 0a 73 75 62 74 72 65 65 | 73 20 69 73 20 66 69 78 |.subtree|s is fix|
|000035d0| 65 64 20 72 65 6c 61 74 | 69 76 65 20 74 6f 20 74 |ed relat|ive to t|
|000035e0| 68 65 69 72 20 70 61 72 | 65 6e 74 2c 20 77 68 69 |heir par|ent, whi|
|000035f0| 63 68 20 69 73 20 63 65 | 6e 74 65 72 65 64 20 6f |ch is ce|ntered o|
|00003600| 76 65 72 20 74 68 65 6d | 2e 0a 41 73 73 75 72 65 |ver them|..Assure|
|00003610| 64 20 74 68 61 74 20 74 | 68 65 20 73 75 62 74 72 |d that t|he subtr|
|00003620| 65 65 73 20 77 69 6c 6c | 20 6e 65 76 65 72 20 62 |ees will| never b|
|00003630| 65 20 70 6c 61 63 65 64 | 20 63 6c 6f 73 65 72 20 |e placed| closer |
|00003640| 74 6f 67 65 74 68 65 72 | 2c 0a 74 68 65 20 70 6f |together|,.the po|
|00003650| 73 74 6f 72 64 65 72 20 | 74 72 61 76 65 72 73 61 |storder |traversa|
|00003660| 6c 20 69 73 20 63 6f 6e | 74 69 6e 75 65 64 2e 0a |l is con|tinued..|
|00003670| 0a 41 20 6e 6f 6e 74 72 | 69 76 69 61 6c 20 69 6d |.A nontr|ivial im|
|00003680| 70 6c 65 6d 65 6e 74 61 | 74 69 6f 6e 20 6f 66 0a |plementa|tion of.|
|00003690| 74 68 69 73 20 61 6c 67 | 6f 72 69 74 68 6d 20 68 |this alg|orithm h|
|000036a0| 61 73 20 62 65 65 6e 20 | 6f 62 74 61 69 6e 65 64 |as been |obtained|
|000036b0| 20 62 79 20 52 65 69 6e | 67 6f 6c 64 20 61 6e 64 | by Rein|gold and|
|000036c0| 20 54 69 6c 66 6f 72 64 | 20 69 6e 7e 5c 63 69 74 | Tilford| in~\cit|
|000036d0| 65 7b 54 69 64 69 65 72 | 54 72 65 65 73 7d 20 0a |e{Tidier|Trees} .|
|000036e0| 74 68 61 74 20 72 75 6e | 73 20 69 6e 20 74 69 6d |that run|s in tim|
|000036f0| 65 20 24 5c 4f 28 4e 29 | 24 2c 20 77 68 65 72 65 |e $\O(N)|$, where|
|00003700| 20 24 4e 24 20 69 73 20 | 74 68 65 20 6e 75 6d 62 | $N$ is |the numb|
|00003710| 65 72 20 6f 66 0a 6e 6f | 64 65 73 20 6f 66 20 74 |er of.no|des of t|
|00003720| 68 65 20 74 72 65 65 20 | 74 6f 20 62 65 20 64 72 |he tree |to be dr|
|00003730| 61 77 6e 2e 0a 54 68 65 | 69 72 20 63 72 75 63 69 |awn..The|ir cruci|
|00003740| 61 6c 20 69 64 65 61 20 | 69 73 20 74 6f 20 6b 65 |al idea |is to ke|
|00003750| 65 70 20 74 72 61 63 6b | 20 6f 66 20 74 68 65 20 |ep track| of the |
|00003760| 63 6f 6e 74 6f 75 72 20 | 6f 66 20 74 68 65 20 73 |contour |of the s|
|00003770| 75 62 74 72 65 65 73 0a | 62 79 20 73 70 65 63 69 |ubtrees.|by speci|
|00003780| 61 6c 20 70 6f 69 6e 74 | 65 72 73 2c 20 63 61 6c |al point|ers, cal|
|00003790| 6c 65 64 20 74 68 72 65 | 61 64 73 2c 20 73 75 63 |led thre|ads, suc|
|000037a0| 68 20 74 68 61 74 20 77 | 68 65 6e 65 76 65 72 0a |h that w|henever.|
|000037b0| 74 77 6f 20 73 75 62 74 | 72 65 65 73 20 61 72 65 |two subt|rees are|
|000037c0| 20 6a 6f 69 6e 65 64 2c | 20 6f 6e 6c 79 20 74 68 | joined,| only th|
|000037d0| 65 0a 74 6f 70 20 70 61 | 72 74 20 6f 66 20 74 68 |e.top pa|rt of th|
|000037e0| 65 20 74 72 65 65 73 20 | 64 6f 77 6e 20 74 6f 20 |e trees |down to |
|000037f0| 74 68 65 20 6c 6f 77 65 | 73 74 20 6c 65 76 65 6c |the lowe|st level|
|00003800| 20 6f 66 20 74 68 65 0a | 73 6d 61 6c 6c 65 72 20 | of the.|smaller |
|00003810| 74 72 65 65 20 6e 65 65 | 64 20 74 6f 20 62 65 20 |tree nee|d to be |
|00003820| 74 61 6b 65 6e 20 69 6e | 74 6f 20 61 63 63 6f 75 |taken in|to accou|
|00003830| 6e 74 2e 0a 0a 54 68 65 | 20 6e 6f 64 65 73 20 61 |nt...The| nodes a|
|00003840| 72 65 20 70 6f 73 69 74 | 69 6f 6e 65 64 20 6f 6e |re posit|ioned on|
|00003850| 20 61 20 66 69 78 65 64 | 20 67 72 69 64 20 61 6e | a fixed| grid an|
|00003860| 64 20 61 72 65 0a 63 6f | 6e 73 69 64 65 72 65 64 |d are.co|nsidered|
|00003870| 20 74 6f 20 68 61 76 65 | 20 7a 65 72 6f 20 77 69 | to have| zero wi|
|00003880| 64 74 68 3b 20 6c 61 62 | 65 6c 69 6e 67 20 69 73 |dth; lab|eling is|
|00003890| 20 6e 6f 74 20 70 72 6f | 76 69 64 65 64 2e 20 0a | not pro|vided. .|
|000038a0| 41 6c 74 68 6f 75 67 68 | 20 74 68 65 20 61 6c 67 |Although| the alg|
|000038b0| 6f 72 69 74 68 6d 20 6f | 6e 6c 79 20 64 72 61 77 |orithm o|nly draw|
|000038c0| 73 20 62 69 6e 61 72 79 | 20 74 72 65 65 73 2c 20 |s binary| trees, |
|000038d0| 69 74 20 69 73 20 65 61 | 73 69 6c 79 20 0a 65 78 |it is ea|sily .ex|
|000038e0| 74 65 6e 64 65 64 20 74 | 6f 20 6d 75 6c 74 69 77 |tended t|o multiw|
|000038f0| 61 79 20 74 72 65 65 73 | 2e 0a 0a 5c 73 65 63 74 |ay trees|...\sect|
|00003900| 69 6f 6e 7b 49 6d 70 72 | 6f 76 69 6e 67 20 68 75 |ion{Impr|oving hu|
|00003910| 6d 61 6e 20 70 65 72 63 | 65 70 74 69 6f 6e 20 6f |man perc|eption o|
|00003920| 66 20 74 72 65 65 73 7d | 0a 0a 49 74 20 69 73 20 |f trees}|..It is |
|00003930| 63 6f 6d 6d 6f 6e 20 75 | 6e 64 65 72 73 74 61 6e |common u|nderstan|
|00003940| 64 69 6e 67 20 69 6e 20 | 62 6f 6f 6b 20 64 65 73 |ding in |book des|
|00003950| 69 67 6e 20 74 68 61 74 | 20 61 65 73 74 68 65 74 |ign that| aesthet|
|00003960| 69 63 73 20 61 6e 64 20 | 72 65 61 64 61 62 69 6c |ics and |readabil|
|00003970| 69 74 79 0a 64 6f 6e 27 | 74 20 6e 65 63 65 73 73 |ity.don'|t necess|
|00003980| 61 72 69 6c 79 20 63 6f | 69 6e 63 69 64 65 2c 20 |arily co|incide, |
|00003990| 61 6e 64 2d 2d 2d 61 73 | 20 4c 61 6d 70 6f 72 74 |and---as| Lamport|
|000039a0| 20 28 5c 63 69 74 65 7b | 4c 61 54 65 58 7d 29 20 | (\cite{|LaTeX}) |
|000039b0| 70 75 74 73 20 69 74 2d | 2d 2d 25 0a 60 60 64 6f |puts it-|--%.``do|
|000039c0| 63 75 6d 65 6e 74 73 20 | 61 72 65 20 6d 65 61 6e |cuments |are mean|
|000039d0| 74 20 74 6f 20 62 65 20 | 72 65 61 64 2c 20 6e 6f |t to be |read, no|
|000039e0| 74 20 68 75 6e 67 20 69 | 6e 20 6d 75 73 65 75 6d |t hung i|n museum|
|000039f0| 73 2e 27 27 20 0a 54 68 | 65 72 65 66 6f 72 65 2c |s.'' .Th|erefore,|
|00003a00| 20 72 65 61 64 61 62 69 | 6c 69 74 79 20 69 73 20 | readabi|lity is |
|00003a10| 6d 6f 72 65 20 69 6d 70 | 6f 72 74 61 6e 74 20 74 |more imp|ortant t|
|00003a20| 68 61 6e 20 61 65 73 74 | 68 65 74 69 63 73 2e 0a |han aest|hetics..|
|00003a30| 0a 57 68 65 6e 20 69 74 | 20 63 6f 6d 65 73 20 74 |.When it| comes t|
|00003a40| 6f 20 74 72 65 65 20 64 | 72 61 77 69 6e 67 73 2c |o tree d|rawings,|
|00003a50| 20 72 65 61 64 61 62 69 | 6c 69 74 79 20 6d 65 61 | readabi|lity mea|
|00003a60| 6e 73 20 74 68 61 74 20 | 74 68 65 20 73 74 72 75 |ns that |the stru|
|00003a70| 63 74 75 72 65 20 6f 66 | 0a 61 20 74 72 65 65 20 |cture of|.a tree |
|00003a80| 6d 75 73 74 20 62 65 20 | 65 61 73 69 6c 79 20 72 |must be |easily r|
|00003a90| 65 63 6f 67 6e 69 7a 61 | 62 6c 65 2e 20 54 68 69 |ecogniza|ble. Thi|
|00003aa0| 73 20 63 72 69 74 65 72 | 69 6f 6e 20 69 73 20 6e |s criter|ion is n|
|00003ab0| 6f 74 20 61 6c 77 61 79 | 73 20 6d 65 74 0a 62 79 |ot alway|s met.by|
|00003ac0| 20 74 68 65 20 52 54 7e | 61 6c 67 6f 72 69 74 68 | the RT~|algorith|
|00003ad0| 6d 2e 20 41 73 20 61 6e | 20 65 78 61 6d 70 6c 65 |m. As an| example|
|00003ae0| 2c 20 74 68 65 72 65 20 | 61 72 65 20 74 72 65 65 |, there |are tree|
|00003af0| 73 20 77 68 6f 73 65 20 | 73 74 72 75 63 74 75 72 |s whose |structur|
|00003b00| 65 20 69 73 20 0a 64 69 | 66 66 65 72 65 6e 74 20 |e is .di|fferent |
|00003b10| 65 76 65 6e 20 74 68 6f | 75 67 68 20 74 68 65 79 |even tho|ugh they|
|00003b20| 20 68 61 76 65 20 74 68 | 65 20 73 61 6d 65 20 6e | have th|e same n|
|00003b30| 75 6d 62 65 72 0a 6f 66 | 20 6e 6f 64 65 73 20 6f |umber.of| nodes o|
|00003b40| 6e 20 65 61 63 68 20 6c | 65 76 65 6c 2e 20 54 68 |n each l|evel. Th|
|00003b50| 65 20 52 54 7e 61 6c 67 | 6f 72 69 74 68 6d 20 6d |e RT~alg|orithm m|
|00003b60| 69 67 68 74 20 61 73 73 | 69 67 6e 20 69 64 65 6e |ight ass|ign iden|
|00003b70| 74 69 63 61 6c 20 70 6f | 73 69 74 69 6f 6e 73 20 |tical po|sitions |
|00003b80| 74 6f 0a 74 68 65 73 65 | 20 6e 6f 64 65 73 20 6d |to.these| nodes m|
|00003b90| 61 6b 69 6e 67 20 69 74 | 20 76 65 72 79 20 68 61 |aking it| very ha|
|00003ba0| 72 64 20 74 6f 20 70 65 | 72 63 65 69 76 65 20 74 |rd to pe|rceive t|
|00003bb0| 68 65 20 73 74 72 75 63 | 74 75 72 61 6c 20 64 69 |he struc|tural di|
|00003bc0| 66 66 65 72 65 6e 63 65 | 73 2e 0a 48 65 6e 63 65 |fference|s..Hence|
|00003bd0| 2c 20 77 65 20 68 61 76 | 65 20 6d 6f 64 69 66 69 |, we hav|e modifi|
|00003be0| 65 64 20 74 68 65 20 52 | 54 7e 61 6c 67 6f 72 69 |ed the R|T~algori|
|00003bf0| 74 68 6d 20 73 75 63 68 | 20 74 68 61 74 20 61 64 |thm such| that ad|
|00003c00| 64 69 74 69 6f 6e 61 6c | 20 77 68 69 74 65 20 73 |ditional| white s|
|00003c10| 70 61 63 65 0a 69 73 20 | 69 6e 73 65 72 74 65 64 |pace.is |inserted|
|00003c20| 20 62 65 74 77 65 65 6e | 20 73 75 62 74 72 65 65 | between| subtree|
|00003c30| 73 20 6f 66 0a 5c 65 6d | 70 68 7b 73 69 67 6e 69 |s of.\em|ph{signi|
|00003c40| 66 69 63 61 6e 74 7d 20 | 6e 6f 64 65 73 2e 20 48 |ficant} |nodes. H|
|00003c50| 65 72 65 20 61 20 62 69 | 6e 61 72 79 20 6e 6f 64 |ere a bi|nary nod|
|00003c60| 65 0a 69 73 20 63 61 6c | 6c 65 64 20 73 69 67 6e |e.is cal|led sign|
|00003c70| 69 66 69 63 61 6e 74 20 | 69 66 20 74 68 65 20 6d |ificant |if the m|
|00003c80| 69 6e 69 6d 75 6d 20 64 | 69 73 74 61 6e 63 65 0a |inimum d|istance.|
|00003c90| 62 65 74 77 65 65 6e 20 | 69 74 73 20 74 77 6f 20 |between |its two |
|00003ca0| 73 75 62 74 72 65 65 73 | 20 69 73 20 61 63 68 69 |subtrees| is achi|
|00003cb0| 65 76 65 64 20 5c 65 6d | 70 68 7b 62 65 6c 6f 77 |eved \em|ph{below|
|00003cc0| 7d 20 74 68 65 69 72 20 | 72 6f 6f 74 20 6c 65 76 |} their |root lev|
|00003cd0| 65 6c 2e 0a 53 65 74 74 | 69 6e 67 20 74 68 65 20 |el..Sett|ing the |
|00003ce0| 61 6d 6f 75 6e 74 20 6f | 66 20 61 64 64 69 74 69 |amount o|f additi|
|00003cf0| 6f 6e 61 6c 20 77 68 69 | 74 65 20 73 70 61 63 65 |onal whi|te space|
|00003d00| 20 74 6f 20 7a 65 72 6f | 20 72 65 74 61 69 6e 73 | to zero| retains|
|00003d10| 20 74 68 65 20 6f 72 69 | 67 69 6e 61 6c 20 52 54 | the ori|ginal RT|
|00003d20| 7e 25 0a 70 6c 61 63 65 | 6d 65 6e 74 2e 20 54 68 |~%.place|ment. Th|
|00003d30| 65 20 65 66 66 65 63 74 | 20 6f 66 20 68 61 76 69 |e effect| of havi|
|00003d40| 6e 67 20 6e 6f 6e 7a 65 | 72 6f 20 61 64 64 69 74 |ng nonze|ro addit|
|00003d50| 69 6f 6e 61 6c 20 77 68 | 69 74 65 20 73 70 61 63 |ional wh|ite spac|
|00003d60| 65 20 62 65 74 77 65 65 | 6e 0a 74 68 65 20 73 75 |e betwee|n.the su|
|00003d70| 62 74 72 65 65 73 20 6f | 66 20 73 69 67 6e 69 66 |btrees o|f signif|
|00003d80| 69 63 61 6e 74 0a 6e 6f | 64 65 73 20 69 73 20 69 |icant.no|des is i|
|00003d90| 6c 6c 75 73 74 72 61 74 | 65 64 20 69 6e 20 5c 66 |llustrat|ed in \f|
|00003da0| 69 67 7b 61 64 64 73 70 | 61 63 65 7d 2e 0a 0a 41 |ig{addsp|ace}...A|
|00003db0| 6e 6f 74 68 65 72 20 66 | 65 61 74 75 72 65 20 77 |nother f|eature w|
|00003dc0| 65 20 68 61 76 65 20 61 | 64 64 65 64 20 74 6f 20 |e have a|dded to |
|00003dd0| 74 68 65 20 52 54 7e 61 | 6c 67 6f 72 69 74 68 6d |the RT~a|lgorithm|
|00003de0| 73 20 69 73 20 74 68 65 | 20 70 6f 73 73 69 62 69 |s is the| possibi|
|00003df0| 6c 69 74 79 20 74 6f 20 | 64 72 61 77 0a 61 6e 20 |lity to |draw.an |
|00003e00| 75 6e 65 78 74 65 6e 64 | 65 64 20 62 69 6e 61 72 |unextend|ed binar|
|00003e10| 79 20 74 72 65 65 20 77 | 69 74 68 20 74 68 65 20 |y tree w|ith the |
|00003e20| 73 61 6d 65 20 70 6c 61 | 63 65 6d 65 6e 74 20 6f |same pla|cement o|
|00003e30| 66 20 6e 6f 64 65 73 20 | 61 73 20 69 74 73 0a 61 |f nodes |as its.a|
|00003e40| 73 73 6f 63 69 61 74 65 | 64 20 65 78 74 65 6e 64 |ssociate|d extend|
|00003e50| 65 64 20 76 65 72 73 69 | 6f 6e 3b 0a 74 68 69 73 |ed versi|on;.this|
|00003e60| 20 6d 61 6b 65 73 20 74 | 68 65 20 73 74 72 75 63 | makes t|he struc|
|00003e70| 74 75 72 65 20 6f 66 20 | 61 20 74 72 65 65 20 6d |ture of |a tree m|
|00003e80| 6f 72 65 20 70 72 6f 6d | 69 6e 65 6e 74 3b 20 73 |ore prom|inent; s|
|00003e90| 65 65 20 5c 66 69 67 7b | 65 78 74 65 6e 64 65 64 |ee \fig{|extended|
|00003ea0| 7d 2e 0a 57 65 20 64 65 | 66 69 6e 65 20 74 68 65 |}..We de|fine the|
|00003eb0| 20 5c 65 6d 70 68 7b 61 | 73 73 6f 63 69 61 74 65 | \emph{a|ssociate|
|00003ec0| 64 20 65 78 74 65 6e 64 | 65 64 20 76 65 72 73 69 |d extend|ed versi|
|00003ed0| 6f 6e 7d 0a 6f 66 20 61 | 20 62 69 6e 61 72 79 20 |on}.of a| binary |
|00003ee0| 74 72 65 65 20 74 6f 20 | 62 65 20 74 68 65 20 62 |tree to |be the b|
|00003ef0| 69 6e 61 72 79 20 74 72 | 65 65 20 6f 62 74 61 69 |inary tr|ee obtai|
|00003f00| 6e 65 64 20 62 79 20 72 | 65 70 6c 61 63 69 6e 67 |ned by r|eplacing|
|00003f10| 20 65 61 63 68 20 65 6d | 70 74 79 20 73 75 62 74 | each em|pty subt|
|00003f20| 72 65 65 0a 68 61 76 69 | 6e 67 20 61 20 6e 6f 6e |ree.havi|ng a non|
|00003f30| 65 6d 70 74 79 20 73 69 | 62 6c 69 6e 67 20 77 69 |empty si|bling wi|
|00003f40| 74 68 20 61 20 73 75 62 | 74 72 65 65 20 63 6f 6e |th a sub|tree con|
|00003f50| 73 69 73 74 69 6e 67 20 | 6f 66 20 6f 6e 65 20 6e |sisting |of one n|
|00003f60| 6f 64 65 2e 20 0a 0a 5c | 62 65 67 69 6e 7b 46 69 |ode. ..\|begin{Fi|
|00003f70| 67 75 72 65 7d 0a 5c 63 | 65 6e 74 65 72 69 6e 67 |gure}.\c|entering|
|00003f80| 0a 5c 6c 65 61 76 65 76 | 6d 6f 64 65 5c 6e 6f 69 |.\leavev|mode\noi|
|00003f90| 6e 64 65 6e 74 0a 5c 62 | 65 67 69 6e 7b 54 72 65 |ndent.\b|egin{Tre|
|00003fa0| 65 7d 0a 5c 65 5c 69 6c | 5c 65 5c 65 5c 69 5c 69 |e}.\e\il|\e\e\i\i|
|00003fb0| 5c 69 6c 20 25 20 74 68 | 65 20 6c 65 66 74 20 73 |\il % th|e left s|
|00003fc0| 75 62 74 72 65 65 0a 5c | 65 5c 69 72 5c 69 6c 20 |ubtree.\|e\ir\il |
|00003fd0| 25 20 74 68 65 20 72 69 | 67 68 74 20 73 75 62 74 |% the ri|ght subt|
|00003fe0| 72 65 65 0a 5c 69 0a 5c | 65 6e 64 7b 54 72 65 65 |ree.\i.\|end{Tree|
|00003ff0| 7d 0a 5c 68 73 6b 69 70 | 5c 6c 65 66 74 64 69 73 |}.\hskip|\leftdis|
|00004000| 74 5c 62 6f 78 5c 54 65 | 58 54 72 65 65 5c 68 73 |t\box\Te|XTree\hs|
|00004010| 6b 69 70 5c 72 69 67 68 | 74 64 69 73 74 5c 71 71 |kip\righ|tdist\qq|
|00004020| 75 61 64 0a 5c 62 65 67 | 69 6e 7b 54 72 65 65 7d |uad.\beg|in{Tree}|
|00004030| 0a 5c 65 5c 69 6c 5c 69 | 6c 5c 69 6c 20 25 20 74 |.\e\il\i|l\il % t|
|00004040| 68 65 20 6c 65 66 74 20 | 73 75 62 74 72 65 65 0a |he left |subtree.|
|00004050| 5c 65 5c 65 5c 69 5c 65 | 5c 69 5c 69 6c 20 25 20 |\e\e\i\e|\i\il % |
|00004060| 74 68 65 20 72 69 67 68 | 74 20 73 75 62 74 72 65 |the righ|t subtre|
|00004070| 65 0a 5c 69 0a 5c 65 6e | 64 7b 54 72 65 65 7d 0a |e.\i.\en|d{Tree}.|
|00004080| 5c 68 73 6b 69 70 5c 6c | 65 66 74 64 69 73 74 5c |\hskip\l|eftdist\|
|00004090| 62 6f 78 5c 54 65 58 54 | 72 65 65 5c 68 73 6b 69 |box\TeXT|ree\hski|
|000040a0| 70 5c 72 69 67 68 74 64 | 69 73 74 5c 71 71 75 61 |p\rightd|ist\qqua|
|000040b0| 64 0a 5c 61 64 64 73 40 | 70 31 30 70 74 0a 5c 62 |d.\adds@|p10pt.\b|
|000040c0| 65 67 69 6e 7b 54 72 65 | 65 7d 0a 5c 65 5c 69 6c |egin{Tre|e}.\e\il|
|000040d0| 5c 65 5c 65 5c 69 5c 6e | 6f 64 65 7b 5c 74 79 70 |\e\e\i\n|ode{\typ|
|000040e0| 65 7b 64 6f 74 7d 5c 6c | 66 74 7b 24 5c 6c 6f 6e |e{dot}\l|ft{$\lon|
|000040f0| 67 72 69 67 68 74 61 72 | 72 6f 77 24 7d 7d 5c 69 |grightar|row$}}\i|
|00004100| 6c 20 25 20 74 68 65 20 | 6c 65 66 74 20 73 75 62 |l % the |left sub|
|00004110| 74 72 65 65 0a 5c 65 5c | 69 72 5c 69 6c 20 25 20 |tree.\e\|ir\il % |
|00004120| 74 68 65 20 72 69 67 68 | 74 20 73 75 62 74 72 65 |the righ|t subtre|
|00004130| 65 0a 5c 6e 6f 64 65 7b | 5c 74 79 70 65 7b 64 6f |e.\node{|\type{do|
|00004140| 74 7d 5c 6c 66 74 7b 24 | 5c 6c 6f 6e 67 72 69 67 |t}\lft{$|\longrig|
|00004150| 68 74 61 72 72 6f 77 24 | 7d 7d 0a 5c 65 6e 64 7b |htarrow$|}}.\end{|
|00004160| 54 72 65 65 7d 0a 5c 68 | 73 6b 69 70 5c 6c 65 66 |Tree}.\h|skip\lef|
|00004170| 74 64 69 73 74 5c 62 6f | 78 5c 54 65 58 54 72 65 |tdist\bo|x\TeXTre|
|00004180| 65 5c 68 73 6b 69 70 5c | 72 69 67 68 74 64 69 73 |e\hskip\|rightdis|
|00004190| 74 5c 71 71 75 61 64 0a | 5c 62 65 67 69 6e 7b 54 |t\qquad.|\begin{T|
|000041a0| 72 65 65 7d 0a 5c 65 5c | 69 6c 5c 69 6c 5c 69 6c |ree}.\e\|il\il\il|
|000041b0| 20 25 20 74 68 65 20 6c | 65 66 74 20 73 75 62 74 | % the l|eft subt|
|000041c0| 72 65 65 0a 5c 65 5c 65 | 5c 69 5c 65 5c 69 5c 69 |ree.\e\e|\i\e\i\i|
|000041d0| 6c 20 25 20 74 68 65 20 | 72 69 67 68 74 20 73 75 |l % the |right su|
|000041e0| 62 74 72 65 65 0a 5c 6e | 6f 64 65 7b 5c 74 79 70 |btree.\n|ode{\typ|
|000041f0| 65 7b 64 6f 74 7d 5c 6c | 66 74 7b 24 5c 6c 6f 6e |e{dot}\l|ft{$\lon|
|00004200| 67 72 69 67 68 74 61 72 | 72 6f 77 24 7d 7d 0a 5c |grightar|row$}}.\|
|00004210| 65 6e 64 7b 54 72 65 65 | 7d 0a 5c 68 73 6b 69 70 |end{Tree|}.\hskip|
|00004220| 5c 6c 65 66 74 64 69 73 | 74 5c 62 6f 78 5c 54 65 |\leftdis|t\box\Te|
|00004230| 58 54 72 65 65 5c 68 73 | 6b 69 70 5c 72 69 67 68 |XTree\hs|kip\righ|
|00004240| 74 64 69 73 74 5c 0a 5c | 61 64 64 73 40 70 30 70 |tdist\.\|adds@p0p|
|00004250| 74 0a 0a 5c 63 61 70 74 | 69 6f 6e 7b 54 68 65 20 |t..\capt|ion{The |
|00004260| 6e 6f 64 65 73 20 6f 66 | 20 74 68 65 20 66 69 72 |nodes of| the fir|
|00004270| 73 74 20 74 77 6f 20 74 | 72 65 65 73 20 61 72 65 |st two t|rees are|
|00004280| 20 70 6c 61 63 65 64 20 | 69 6e 20 74 68 65 20 73 | placed |in the s|
|00004290| 61 6d 65 20 70 6f 73 69 | 74 69 6f 6e 73 0a 62 79 |ame posi|tions.by|
|000042a0| 20 74 68 65 20 52 54 7e | 61 6c 67 6f 72 69 74 68 | the RT~|algorith|
|000042b0| 6d 2c 20 61 6c 74 68 6f | 75 67 68 20 74 68 65 20 |m, altho|ugh the |
|000042c0| 73 74 72 75 63 74 75 72 | 65 20 6f 66 20 74 68 65 |structur|e of the|
|000042d0| 20 74 77 6f 20 74 72 65 | 65 73 20 69 73 20 64 69 | two tre|es is di|
|000042e0| 66 66 65 72 65 6e 74 2e | 0a 54 68 65 20 61 6c 74 |fferent.|.The alt|
|000042f0| 65 72 6e 61 74 69 76 65 | 20 64 72 61 77 69 6e 67 |ernative| drawing|
|00004300| 73 20 68 69 67 68 6c 69 | 67 68 74 20 74 68 65 20 |s highli|ght the |
|00004310| 73 74 72 75 63 74 75 72 | 61 6c 20 64 69 66 66 65 |structur|al diffe|
|00004320| 72 65 6e 63 65 73 20 0a | 6f 66 20 74 68 65 20 74 |rences .|of the t|
|00004330| 72 65 65 73 20 62 79 20 | 61 64 64 69 6e 67 20 61 |rees by |adding a|
|00004340| 64 64 69 74 69 6f 6e 61 | 6c 20 77 68 69 74 65 20 |dditiona|l white |
|00004350| 73 70 61 63 65 20 62 65 | 74 77 65 65 6e 20 74 68 |space be|tween th|
|00004360| 65 20 73 75 62 74 72 65 | 65 73 20 6f 66 0a 28 24 |e subtre|es of.($|
|00004370| 5c 6c 6f 6e 67 72 69 67 | 68 74 61 72 72 6f 77 24 |\longrig|htarrow$|
|00004380| 29 20 73 69 67 6e 69 66 | 69 63 61 6e 74 20 6e 6f |) signif|icant no|
|00004390| 64 65 73 2e 7d 0a 5c 6c | 61 62 65 6c 7b 61 64 64 |des.}.\l|abel{add|
|000043a0| 73 70 61 63 65 7d 0a 5c | 65 6e 64 7b 46 69 67 75 |space}.\|end{Figu|
|000043b0| 72 65 7d 0a 0a 5c 62 65 | 67 69 6e 7b 46 69 67 75 |re}..\be|gin{Figu|
|000043c0| 72 65 7d 0a 5c 63 65 6e | 74 65 72 69 6e 67 0a 5c |re}.\cen|tering.\|
|000043d0| 6c 65 61 76 65 76 6d 6f | 64 65 5c 6e 6f 69 6e 64 |leavevmo|de\noind|
|000043e0| 65 6e 74 0a 5c 62 65 67 | 69 6e 7b 54 72 65 65 7d |ent.\beg|in{Tree}|
|000043f0| 0a 5c 65 5c 65 5c 69 5c | 69 6c 5c 65 5c 65 5c 69 |.\e\e\i\|il\e\e\i|
|00004400| 5c 69 0a 5c 65 6e 64 7b | 54 72 65 65 7d 0a 5c 68 |\i.\end{|Tree}.\h|
|00004410| 73 6b 69 70 5c 6c 65 66 | 74 64 69 73 74 5c 62 6f |skip\lef|tdist\bo|
|00004420| 78 5c 54 65 58 54 72 65 | 65 5c 68 73 6b 69 70 5c |x\TeXTre|e\hskip\|
|00004430| 72 69 67 68 74 64 69 73 | 74 5c 68 62 6f 78 7b 7d |rightdis|t\hbox{}|
|00004440| 5c 71 71 75 61 64 0a 5c | 62 65 67 69 6e 7b 54 72 |\qquad.\|begin{Tr|
|00004450| 65 65 7d 0a 5c 65 5c 65 | 5c 69 5c 65 5c 69 5c 65 |ee}.\e\e|\i\e\i\e|
|00004460| 5c 69 72 5c 69 0a 5c 65 | 6e 64 7b 54 72 65 65 7d |\ir\i.\e|nd{Tree}|
|00004470| 0a 5c 68 73 6b 69 70 5c | 6c 65 66 74 64 69 73 74 |.\hskip\|leftdist|
|00004480| 5c 62 6f 78 5c 54 65 58 | 54 72 65 65 5c 68 73 6b |\box\TeX|Tree\hsk|
|00004490| 69 70 5c 72 69 67 68 74 | 64 69 73 74 5c 68 62 6f |ip\right|dist\hbo|
|000044a0| 78 7b 7d 5c 5c 0a 5c 65 | 78 74 65 6e 64 65 64 0a |x{}\\.\e|xtended.|
|000044b0| 5c 62 65 67 69 6e 7b 54 | 72 65 65 7d 0a 5c 65 5c |\begin{T|ree}.\e\|
|000044c0| 65 5c 69 5c 69 6c 5c 65 | 5c 65 5c 69 5c 69 0a 5c |e\i\il\e|\e\i\i.\|
|000044d0| 65 6e 64 7b 54 72 65 65 | 7d 0a 5c 68 73 6b 69 70 |end{Tree|}.\hskip|
|000044e0| 5c 6c 65 66 74 64 69 73 | 74 5c 62 6f 78 5c 54 65 |\leftdis|t\box\Te|
|000044f0| 58 54 72 65 65 5c 68 73 | 6b 69 70 5c 72 69 67 68 |XTree\hs|kip\righ|
|00004500| 74 64 69 73 74 5c 68 62 | 6f 78 7b 7d 5c 71 71 75 |tdist\hb|ox{}\qqu|
|00004510| 61 64 0a 5c 62 65 67 69 | 6e 7b 54 72 65 65 7d 0a |ad.\begi|n{Tree}.|
|00004520| 5c 65 5c 65 5c 69 5c 65 | 5c 69 5c 65 5c 69 72 5c |\e\e\i\e|\i\e\ir\|
|00004530| 69 0a 5c 65 6e 64 7b 54 | 72 65 65 7d 0a 5c 68 73 |i.\end{T|ree}.\hs|
|00004540| 6b 69 70 5c 6c 65 66 74 | 64 69 73 74 5c 62 6f 78 |kip\left|dist\box|
|00004550| 5c 54 65 58 54 72 65 65 | 5c 68 73 6b 69 70 5c 72 |\TeXTree|\hskip\r|
|00004560| 69 67 68 74 64 69 73 74 | 5c 68 62 6f 78 7b 7d 5c |ightdist|\hbox{}\|
|00004570| 5c 0a 5c 6e 6f 65 78 74 | 65 6e 64 65 64 0a 5c 62 |\.\noext|ended.\b|
|00004580| 65 67 69 6e 7b 54 72 65 | 65 7d 0a 5c 65 5c 65 5c |egin{Tre|e}.\e\e\|
|00004590| 69 5c 65 5c 69 5c 65 5c | 65 5c 69 5c 69 0a 5c 65 |i\e\i\e\|e\i\i.\e|
|000045a0| 6e 64 7b 54 72 65 65 7d | 0a 5c 68 73 6b 69 70 5c |nd{Tree}|.\hskip\|
|000045b0| 6c 65 66 74 64 69 73 74 | 5c 62 6f 78 5c 54 65 58 |leftdist|\box\TeX|
|000045c0| 54 72 65 65 5c 68 73 6b | 69 70 5c 72 69 67 68 74 |Tree\hsk|ip\right|
|000045d0| 64 69 73 74 5c 0a 5c 63 | 61 70 74 69 6f 6e 7b 41 |dist\.\c|aption{A|
|000045e0| 73 20 69 6e 20 74 68 65 | 20 70 72 65 76 69 6f 75 |s in the| previou|
|000045f0| 73 20 66 69 67 75 72 65 | 2c 20 74 68 65 20 6e 6f |s figure|, the no|
|00004600| 64 65 73 20 6f 66 20 74 | 68 65 20 66 69 72 73 74 |des of t|he first|
|00004610| 20 74 77 6f 20 74 72 65 | 65 73 0a 61 72 65 20 70 | two tre|es.are p|
|00004620| 6c 61 63 65 64 20 69 6e | 20 74 68 65 20 73 61 6d |laced in| the sam|
|00004630| 65 20 70 6f 73 69 74 69 | 6f 6e 20 62 79 20 74 68 |e positi|on by th|
|00004640| 65 20 52 54 20 61 6c 67 | 6f 72 69 74 68 6d 2c 0a |e RT alg|orithm,.|
|00004650| 61 6c 74 68 6f 75 67 68 | 20 74 68 65 69 72 20 73 |although| their s|
|00004660| 74 72 75 63 74 75 72 65 | 20 69 73 20 64 69 66 66 |tructure| is diff|
|00004670| 65 72 65 6e 74 2e 20 54 | 68 65 20 6d 6f 64 69 66 |erent. T|he modif|
|00004680| 69 65 64 0a 52 54 7e 61 | 6c 67 6f 72 69 74 68 6d |ied.RT~a|lgorithm|
|00004690| 73 20 68 69 67 68 6c 69 | 67 68 74 73 20 74 68 65 |s highli|ghts the|
|000046a0| 20 73 74 72 75 63 74 75 | 72 61 6c 20 64 69 66 66 | structu|ral diff|
|000046b0| 65 72 65 6e 63 65 73 20 | 6f 66 20 74 68 65 20 74 |erences |of the t|
|000046c0| 72 65 65 73 20 62 79 20 | 0a 64 72 61 77 69 6e 67 |rees by |.drawing|
|000046d0| 20 74 68 65 6d 20 6c 69 | 6b 65 20 74 68 65 69 72 | them li|ke their|
|000046e0| 20 69 64 65 6e 74 69 63 | 61 6c 20 65 78 74 65 6e | identic|al exten|
|000046f0| 64 65 64 0a 76 65 72 73 | 69 6f 6e 20 28 67 69 76 |ded.vers|ion (giv|
|00004700| 65 6e 20 69 6e 20 74 68 | 65 20 74 68 69 72 64 20 |en in th|e third |
|00004710| 72 6f 77 29 2c 20 62 75 | 74 20 73 75 70 70 72 65 |row), bu|t suppre|
|00004720| 73 73 69 6e 67 20 74 68 | 65 20 61 64 64 69 74 69 |ssing th|e additi|
|00004730| 6f 6e 61 6c 20 6e 6f 64 | 65 73 2e 7d 0a 5c 6c 61 |onal nod|es.}.\la|
|00004740| 62 65 6c 7b 65 78 74 65 | 6e 64 65 64 7d 0a 5c 65 |bel{exte|nded}.\e|
|00004750| 6e 64 7b 46 69 67 75 72 | 65 7d 0a 0a 0a 5c 73 65 |nd{Figur|e}...\se|
|00004760| 63 74 69 6f 6e 7b 54 72 | 65 65 73 20 69 6e 20 61 |ction{Tr|ees in a|
|00004770| 20 64 6f 63 75 6d 65 6e | 74 20 70 72 65 70 61 72 | documen|t prepar|
|00004780| 61 74 69 6f 6e 20 65 6e | 76 69 72 6f 6e 6d 65 6e |ation en|vironmen|
|00004790| 74 7d 0a 0a 44 72 61 77 | 69 6e 67 73 20 6f 66 20 |t}..Draw|ings of |
|000047a0| 74 72 65 65 73 20 64 6f | 20 6e 6f 74 20 75 73 75 |trees do| not usu|
|000047b0| 61 6c 6c 79 20 61 70 70 | 65 61 72 20 62 79 20 74 |ally app|ear by t|
|000047c0| 68 65 6d 73 65 6c 76 65 | 73 2c 0a 62 75 74 20 61 |hemselve|s,.but a|
|000047d0| 72 65 20 69 6e 63 6c 75 | 64 65 64 20 69 6e 20 73 |re inclu|ded in s|
|000047e0| 6f 6d 65 20 74 65 78 74 | 0a 74 68 61 74 20 69 73 |ome text|.that is|
|000047f0| 20 69 74 73 65 6c 66 20 | 74 79 70 65 73 65 74 20 | itself |typeset |
|00004800| 62 79 20 61 20 74 65 78 | 74 20 70 72 6f 63 65 73 |by a tex|t proces|
|00004810| 73 69 6e 67 20 73 79 73 | 74 65 6d 2e 20 54 68 65 |sing sys|tem. The|
|00004820| 72 65 66 6f 72 65 2c 20 | 61 20 74 79 70 69 63 61 |refore, |a typica|
|00004830| 6c 0a 73 63 65 6e 61 72 | 69 6f 20 69 73 20 61 20 |l.scenar|io is a |
|00004840| 70 69 70 65 20 6f 66 20 | 74 68 72 65 65 20 73 74 |pipe of |three st|
|00004850| 61 67 65 73 2e 20 46 69 | 72 73 74 2c 20 77 65 20 |ages. Fi|rst, we |
|00004860| 68 61 76 65 20 61 20 74 | 72 65 65 20 64 72 61 77 |have a t|ree draw|
|00004870| 69 6e 67 0a 70 72 6f 67 | 72 61 6d 20 74 68 61 74 |ing.prog|ram that|
|00004880| 20 63 61 6c 63 75 6c 61 | 74 65 73 20 74 68 65 20 | calcula|tes the |
|00004890| 70 6f 73 69 74 69 6f 6e | 69 6e 67 20 6f 66 20 74 |position|ing of t|
|000048a0| 68 65 20 6e 6f 64 65 73 | 20 6f 66 20 74 68 65 20 |he nodes| of the |
|000048b0| 74 72 65 65 20 74 6f 0a | 62 65 20 64 72 61 77 6e |tree to.|be drawn|
|000048c0| 20 61 6e 64 20 6f 75 74 | 70 75 74 73 20 61 20 64 | and out|puts a d|
|000048d0| 65 73 63 72 69 70 74 69 | 6f 6e 20 6f 66 20 74 68 |escripti|on of th|
|000048e0| 65 20 74 72 65 65 20 64 | 72 61 77 69 6e 67 20 69 |e tree d|rawing i|
|000048f0| 6e 0a 73 6f 6d 65 20 67 | 72 61 70 68 69 63 73 20 |n.some g|raphics |
|00004900| 6c 61 6e 67 75 61 67 65 | 3b 20 74 68 69 73 20 69 |language|; this i|
|00004910| 73 20 66 6f 6c 6c 6f 77 | 65 64 20 62 79 0a 61 20 |s follow|ed by.a |
|00004920| 67 72 61 70 68 69 63 73 | 20 73 79 73 74 65 6d 20 |graphics| system |
|00004930| 74 68 61 74 20 74 72 61 | 6e 73 66 6f 72 6d 73 20 |that tra|nsforms |
|00004940| 74 68 69 73 0a 64 65 73 | 63 72 69 70 74 69 6f 6e |this.des|cription|
|00004950| 20 69 6e 74 6f 20 61 6e | 20 69 6e 74 65 72 6d 65 | into an| interme|
|00004960| 64 69 61 74 65 20 6c 61 | 6e 67 75 61 67 65 20 74 |diate la|nguage t|
|00004970| 68 61 74 20 63 61 6e 20 | 62 65 20 69 6e 74 65 72 |hat can |be inter|
|00004980| 70 72 65 74 65 64 20 62 | 79 20 74 68 65 20 6f 75 |preted b|y the ou|
|00004990| 74 70 75 74 0a 64 65 76 | 69 63 65 3b 20 61 6e 64 |tput.dev|ice; and|
|000049a0| 2c 20 66 69 6e 61 6c 6c | 79 2c 20 77 65 20 68 61 |, finall|y, we ha|
|000049b0| 76 65 20 74 68 65 0a 74 | 65 78 74 20 70 72 6f 63 |ve the.t|ext proc|
|000049c0| 65 73 73 69 6e 67 20 73 | 79 73 74 65 6d 20 74 68 |essing s|ystem th|
|000049d0| 61 74 20 69 6e 74 65 67 | 72 61 74 65 73 20 74 68 |at integ|rates th|
|000049e0| 65 20 6f 75 74 70 75 74 | 20 6f 66 20 74 68 65 0a |e output| of the.|
|000049f0| 67 72 61 70 68 69 63 73 | 20 73 79 73 74 65 6d 20 |graphics| system |
|00004a00| 69 6e 74 6f 20 74 68 65 | 20 74 65 78 74 2e 0a 0a |into the| text...|
|00004a10| 54 68 69 73 20 73 63 65 | 6e 61 72 69 6f 20 6c 6f |This sce|nario lo|
|00004a20| 73 65 73 20 69 74 73 20 | 6c 69 6e 65 61 72 20 73 |ses its |linear s|
|00004a30| 74 72 75 63 74 75 72 65 | 20 6f 6e 63 65 20 6e 6f |tructure| once no|
|00004a40| 64 65 73 20 68 61 76 65 | 20 74 6f 20 62 65 20 6c |des have| to be l|
|00004a50| 61 62 65 6c 65 64 2c 20 | 73 69 6e 63 65 0a 74 68 |abeled, |since.th|
|00004a60| 65 20 6c 61 62 65 6c 69 | 6e 67 20 69 6e 66 6c 75 |e labeli|ng influ|
|00004a70| 65 6e 63 65 73 20 74 68 | 65 20 70 6f 73 69 74 69 |ences th|e positi|
|00004a80| 6f 6e 69 6e 67 20 6f 66 | 20 74 68 65 20 6e 6f 64 |oning of| the nod|
|00004a90| 65 73 2e 20 4c 61 62 65 | 6c 73 20 75 73 75 61 6c |es. Labe|ls usual|
|00004aa0| 6c 79 20 6f 63 63 75 72 | 0a 69 6e 73 69 64 65 2c |ly occur|.inside,|
|00004ab0| 20 74 6f 20 74 68 65 20 | 6c 65 66 74 20 6f 66 2c | to the |left of,|
|00004ac0| 20 74 6f 20 74 68 65 20 | 72 69 67 68 74 20 6f 66 | to the |right of|
|00004ad0| 2c 20 6f 72 20 62 65 6e | 65 61 74 68 20 6e 6f 64 |, or ben|eath nod|
|00004ae0| 65 73 20 28 74 68 65 20 | 6c 61 74 74 65 72 20 6f |es (the |latter o|
|00004af0| 6e 6c 79 20 66 6f 72 0a | 65 78 74 65 72 6e 61 6c |nly for.|external|
|00004b00| 20 6e 6f 64 65 73 29 2e | 20 54 68 65 69 72 20 77 | nodes).| Their w|
|00004b10| 69 64 74 68 73 20 73 68 | 6f 75 6c 64 20 63 65 72 |idths sh|ould cer|
|00004b20| 74 61 69 6e 6c 79 20 62 | 65 20 74 61 6b 65 6e 20 |tainly b|e taken |
|00004b30| 69 6e 74 6f 20 61 63 63 | 6f 75 6e 74 0a 62 79 20 |into acc|ount.by |
|00004b40| 74 68 65 20 20 74 72 65 | 65 20 64 72 61 77 69 6e |the  tre|e drawin|
|00004b50| 67 20 61 6c 67 6f 72 69 | 74 68 6d 2e 20 42 75 74 |g algori|thm. But|
|00004b60| 20 74 68 65 20 6c 61 62 | 65 6c 73 20 68 61 76 65 | the lab|els have|
|00004b70| 20 74 6f 20 62 65 20 74 | 79 70 65 73 65 74 20 66 | to be t|ypeset f|
|00004b80| 69 72 73 74 0a 74 6f 20 | 64 65 74 65 72 6d 69 6e |irst.to |determin|
|00004b90| 65 20 74 68 65 69 72 20 | 65 78 74 65 6e 73 69 6f |e their |extensio|
|00004ba0| 6e 73 2c 0a 70 72 65 66 | 65 72 61 62 6c 79 20 62 |ns,.pref|erably b|
|00004bb0| 79 20 74 68 65 20 74 79 | 70 65 73 65 74 74 69 6e |y the ty|pesettin|
|00004bc0| 67 20 70 72 6f 67 72 61 | 6d 20 74 68 61 74 0a 69 |g progra|m that.i|
|00004bd0| 73 20 75 73 65 64 20 66 | 6f 72 20 74 68 65 20 72 |s used f|or the r|
|00004be0| 65 67 75 6c 61 72 20 74 | 65 78 74 2c 20 62 65 63 |egular t|ext, bec|
|00004bf0| 61 75 73 65 20 74 68 69 | 73 20 65 6e 73 75 72 65 |ause thi|s ensure|
|00004c00| 73 20 75 6e 69 66 6f 72 | 6d 69 74 79 20 69 6e 20 |s unifor|mity in |
|00004c10| 74 68 65 20 74 65 78 74 | 75 61 6c 0a 70 61 72 74 |the text|ual.part|
|00004c20| 73 20 6f 66 20 74 68 65 | 20 64 6f 63 75 6d 65 6e |s of the| documen|
|00004c30| 74 20 61 6e 64 20 70 72 | 6f 76 69 64 65 73 20 74 |t and pr|ovides t|
|00004c40| 68 65 20 61 75 74 68 6f | 72 20 77 69 74 68 20 74 |he autho|r with t|
|00004c50| 68 65 20 66 75 6c 6c 20 | 70 6f 77 65 72 20 6f 66 |he full |power of|
|00004c60| 20 61 0a 74 65 78 74 20 | 70 72 6f 63 65 73 73 69 | a.text |processi|
|00004c70| 6e 67 20 73 79 73 74 65 | 6d 20 66 6f 72 20 63 6f |ng syste|m for co|
|00004c80| 6d 70 6f 73 69 6e 67 20 | 74 68 65 20 6c 61 62 65 |mposing |the labe|
|00004c90| 6c 73 2e 20 48 65 6e 63 | 65 2c 20 61 20 6d 6f 72 |ls. Henc|e, a mor|
|00004ca0| 65 20 63 6f 6d 70 6c 65 | 78 0a 63 6f 6d 6d 75 6e |e comple|x.commun|
|00004cb0| 69 63 61 74 69 6f 6e 20 | 73 63 68 65 6d 65 20 74 |ication |scheme t|
|00004cc0| 68 61 6e 20 61 20 73 69 | 6d 70 6c 65 20 70 69 70 |han a si|mple pip|
|00004cd0| 65 20 69 73 20 72 65 71 | 75 69 72 65 64 2e 0a 0a |e is req|uired...|
|00004ce0| 41 6c 74 68 6f 75 67 68 | 20 61 20 73 79 73 74 65 |Although| a syste|
|00004cf0| 6d 20 6f 66 20 74 77 6f | 20 70 72 6f 63 65 73 73 |m of two| process|
|00004d00| 65 73 20 72 75 6e 6e 69 | 6e 67 20 73 69 6d 75 6c |es runni|ng simul|
|00004d10| 74 61 6e 65 6f 75 73 6c | 79 20 6d 69 67 68 74 20 |taneousl|y might |
|00004d20| 62 65 20 74 68 65 20 6d | 6f 73 74 0a 65 6c 65 67 |be the m|ost.eleg|
|00004d30| 61 6e 74 20 73 6f 6c 75 | 74 69 6f 6e 2c 20 77 65 |ant solu|tion, we|
|00004d40| 20 77 61 6e 74 65 64 20 | 61 20 73 79 73 74 65 6d | wanted |a system|
|00004d50| 20 74 68 61 74 20 69 73 | 20 65 61 73 69 6c 79 20 | that is| easily |
|00004d60| 70 6f 72 74 61 62 6c 65 | 20 74 6f 0a 77 69 64 65 |portable| to.wide|
|00004d70| 6c 79 20 64 69 66 66 65 | 72 65 6e 74 20 6d 61 63 |ly diffe|rent mac|
|00004d80| 68 69 6e 65 73 20 61 74 | 20 6f 75 72 20 73 69 74 |hines at| our sit|
|00004d90| 65 73 0a 69 6e 63 6c 75 | 64 69 6e 67 20 70 65 72 |es.inclu|ding per|
|00004da0| 73 6f 6e 61 6c 20 63 6f | 6d 70 75 74 65 72 73 20 |sonal co|mputers |
|00004db0| 77 69 74 68 20 73 69 6e | 67 6c 65 20 70 72 6f 63 |with sin|gle proc|
|00004dc0| 65 73 73 0a 6f 70 65 72 | 61 74 69 6e 67 20 73 79 |ess.oper|ating sy|
|00004dd0| 73 74 65 6d 73 2e 0a 54 | 68 65 72 65 66 6f 72 65 |stems..T|herefore|
|00004de0| 2c 20 77 65 20 64 65 63 | 69 64 65 64 20 74 6f 20 |, we dec|ided to |
|00004df0| 75 73 65 20 61 20 74 65 | 78 74 20 70 72 6f 63 65 |use a te|xt proce|
|00004e00| 73 73 69 6e 67 20 73 79 | 73 74 65 6d 0a 68 61 76 |ssing sy|stem.hav|
|00004e10| 69 6e 67 20 70 72 6f 67 | 72 61 6d 6d 69 6e 67 20 |ing prog|ramming |
|00004e20| 66 61 63 69 6c 69 74 69 | 65 73 20 70 6f 77 65 72 |faciliti|es power|
|00004e30| 66 75 6c 20 65 6e 6f 75 | 67 68 20 74 6f 20 0a 70 |ful enou|gh to .p|
|00004e40| 72 6f 67 72 61 6d 20 61 | 20 74 72 65 65 20 64 72 |rogram a| tree dr|
|00004e50| 61 77 69 6e 67 20 61 6c | 67 6f 72 69 74 68 6d 20 |awing al|gorithm |
|00004e60| 61 6e 64 20 67 72 61 70 | 68 69 63 73 20 66 61 63 |and grap|hics fac|
|00004e70| 69 6c 69 74 69 65 73 20 | 70 6f 77 65 72 66 75 6c |ilities |powerful|
|00004e80| 20 65 6e 6f 75 67 68 0a | 74 6f 20 64 72 61 77 20 | enough.|to draw |
|00004e90| 61 20 74 72 65 65 2e 20 | 4f 6e 65 20 74 65 78 74 |a tree. |One text|
|00004ea0| 20 70 72 6f 63 65 73 73 | 69 6e 67 20 73 79 73 74 | process|ing syst|
|00004eb0| 65 6d 0a 72 65 6e 64 65 | 72 69 6e 67 20 6f 75 74 |em.rende|ring out|
|00004ec0| 73 74 61 6e 64 69 6e 67 | 20 74 79 70 6f 67 72 61 |standing| typogra|
|00004ed0| 70 68 69 63 20 71 75 61 | 6c 69 74 79 20 61 6e 64 |phic qua|lity and|
|00004ee0| 20 73 61 74 69 73 66 61 | 63 74 6f 72 79 20 70 72 | satisfa|ctory pr|
|00004ef0| 6f 67 72 61 6d 6d 69 6e | 67 0a 66 61 63 69 6c 69 |ogrammin|g.facili|
|00004f00| 74 69 65 73 20 69 73 20 | 5c 54 65 58 2c 20 64 65 |ties is |\TeX, de|
|00004f10| 76 65 6c 6f 70 65 64 20 | 62 79 20 4b 6e 75 74 68 |veloped |by Knuth|
|00004f20| 20 61 74 20 53 74 61 6e | 66 6f 72 64 20 55 6e 69 | at Stan|ford Uni|
|00004f30| 76 65 72 73 69 74 79 3b | 0a 73 65 65 7e 5c 63 69 |versity;|.see~\ci|
|00004f40| 74 65 7b 54 65 58 62 6f | 6f 6b 7d 2e 0a 54 68 65 |te{TeXbo|ok}..The|
|00004f50| 20 5c 54 65 58 7b 7d 20 | 73 79 73 74 65 6d 20 69 | \TeX{} |system i|
|00004f60| 6e 63 6c 75 64 65 73 20 | 74 68 65 20 66 6f 6c 6c |ncludes |the foll|
|00004f70| 6f 77 69 6e 67 20 70 72 | 6f 67 72 61 6d 6d 69 6e |owing pr|ogrammin|
|00004f80| 67 20 66 61 63 69 6c 69 | 74 69 65 73 2e 0a 0a 5c |g facili|ties...\|
|00004f90| 62 65 67 69 6e 7b 65 6e | 75 6d 65 72 61 74 65 7d |begin{en|umerate}|
|00004fa0| 0a 5c 69 74 65 6d 5b 31 | 2e 5d 20 44 61 74 61 74 |.\item[1|.] Datat|
|00004fb0| 79 70 65 73 3a 5c 5c 0a | 20 20 20 20 20 69 6e 74 |ypes:\\.|     int|
|00004fc0| 65 67 65 72 73 7e 28 32 | 35 36 29 2c 20 64 69 6d |egers~(2|56), dim|
|00004fd0| 65 6e 73 69 6f 6e 73 5c | 66 6f 6f 74 6e 6f 74 65 |ensions\|footnote|
|00004fe0| 7b 54 68 65 20 74 65 72 | 6d 20 5c 65 6d 70 68 7b |{The ter|m \emph{|
|00004ff0| 64 69 6d 65 6e 73 69 6f | 6e 7d 20 69 73 20 75 73 |dimensio|n} is us|
|00005000| 65 64 0a 20 20 20 20 20 | 69 6e 20 5c 54 65 58 5c |ed.     |in \TeX\|
|00005010| 20 74 6f 20 64 65 73 63 | 72 69 62 65 20 70 68 79 | to desc|ribe phy|
|00005020| 73 69 63 61 6c 20 6d 65 | 61 73 75 72 65 6d 65 6e |sical me|asuremen|
|00005030| 74 73 20 6f 66 20 74 79 | 70 6f 67 72 61 70 68 69 |ts of ty|pographi|
|00005040| 63 61 6c 20 6f 62 6a 65 | 63 74 73 3b 0a 20 20 20 |cal obje|cts;.   |
|00005050| 20 20 66 6f 72 20 65 78 | 61 6d 70 6c 65 2c 20 74 |  for ex|ample, t|
|00005060| 68 65 20 6c 65 6e 67 74 | 68 20 6f 66 20 61 20 77 |he lengt|h of a w|
|00005070| 6f 72 64 2e 7d 7e 28 35 | 31 32 29 2c 20 0a 20 20 |ord.}~(5|12), .  |
|00005080| 20 20 20 62 6f 78 65 73 | 7e 28 32 35 36 29 2c 20 |   boxes|~(256), |
|00005090| 74 6f 6b 65 6e 6c 69 73 | 74 73 7e 28 32 35 36 29 |tokenlis|ts~(256)|
|000050a0| 2c 20 61 6e 64 0a 20 20 | 20 20 20 62 6f 6f 6c 65 |, and.  |   boole|
|000050b0| 61 6e 20 76 61 72 69 61 | 62 6c 65 73 7e 28 75 6e |an varia|bles~(un|
|000050c0| 72 65 73 74 72 69 63 74 | 65 64 29 2e 0a 5c 69 74 |restrict|ed)..\it|
|000050d0| 65 6d 5b 32 2e 5d 20 45 | 6c 65 6d 65 6e 74 61 72 |em[2.] E|lementar|
|000050e0| 79 20 73 74 61 74 65 6d | 65 6e 74 73 3a 5c 5c 0a |y statem|ents:\\.|
|000050f0| 20 20 20 20 20 24 61 3a | 3d 5c 72 6d 20 63 6f 6e |     $a:|=\rm con|
|00005100| 73 74 24 2c 20 24 61 3a | 3d 62 24 20 28 61 6c 6c |st$, $a:|=b$ (all|
|00005110| 20 74 79 70 65 73 29 3b | 5c 5c 0a 20 20 20 20 20 | types);|\\.     |
|00005120| 24 61 3a 3d 61 2b 62 24 | 2c 20 24 61 3a 3d 61 2a |$a:=a+b$|, $a:=a*|
|00005130| 62 24 2c 20 24 61 3a 3d | 61 2f 62 24 20 28 69 6e |b$, $a:=|a/b$ (in|
|00005140| 74 65 67 65 72 73 20 61 | 6e 64 20 64 69 6d 65 6e |tegers a|nd dimen|
|00005150| 73 69 6f 6e 73 29 3b 20 | 61 6e 64 5c 5c 0a 20 20 |sions); |and\\.  |
|00005160| 20 20 20 68 6f 72 69 7a | 6f 6e 74 61 6c 20 61 6e |   horiz|ontal an|
|00005170| 64 20 76 65 72 74 69 63 | 61 6c 20 6e 65 73 74 69 |d vertic|al nesti|
|00005180| 6e 67 20 6f 66 20 62 6f | 78 65 73 2e 0a 5c 69 74 |ng of bo|xes..\it|
|00005190| 65 6d 5b 33 2e 5d 20 43 | 6f 6e 74 72 6f 6c 20 63 |em[3.] C|ontrol c|
|000051a0| 6f 6e 73 74 72 75 63 74 | 73 3a 5c 5c 0a 20 20 20 |onstruct|s:\\.   |
|000051b0| 20 20 69 66 2d 74 68 65 | 6e 2d 65 6c 73 65 20 73 |  if-the|n-else s|
|000051c0| 74 61 74 65 6d 65 6e 74 | 73 20 74 65 73 74 69 6e |tatement|s testin|
|000051d0| 67 20 72 65 6c 61 74 69 | 6f 6e 73 20 62 65 74 77 |g relati|ons betw|
|000051e0| 65 65 6e 20 69 6e 74 65 | 67 65 72 73 2c 0a 20 20 |een inte|gers,.  |
|000051f0| 20 20 20 64 69 6d 65 6e | 73 69 6f 6e 73 2c 20 62 |   dimen|sions, b|
|00005200| 6f 78 65 73 2c 20 6f 72 | 20 62 6f 6f 6c 65 61 6e |oxes, or| boolean|
|00005210| 20 76 61 72 69 61 62 6c | 65 73 2e 0a 5c 69 74 65 | variabl|es..\ite|
|00005220| 6d 5b 34 2e 5d 20 4d 6f | 64 75 6c 61 72 69 7a 61 |m[4.] Mo|dulariza|
|00005230| 74 69 6f 6e 20 63 6f 6e | 73 74 72 75 63 74 73 3a |tion con|structs:|
|00005240| 5c 5c 0a 20 20 20 20 20 | 6d 61 63 72 6f 73 20 77 |\\.     |macros w|
|00005250| 69 74 68 20 75 70 20 74 | 6f 20 39 7e 70 61 72 61 |ith up t|o 9~para|
|00005260| 6d 65 74 65 72 73 20 28 | 63 61 6e 20 62 65 20 76 |meters (|can be v|
|00005270| 69 65 77 65 64 20 61 73 | 20 70 72 6f 63 65 64 75 |iewed as| procedu|
|00005280| 72 65 73 20 77 69 74 68 | 6f 75 74 0a 20 20 20 20 |res with|out.    |
|00005290| 20 74 68 65 20 63 6f 6e | 63 65 70 74 20 6f 66 20 | the con|cept of |
|000052a0| 6c 6f 63 61 6c 20 76 61 | 72 69 61 62 6c 65 73 29 |local va|riables)|
|000052b0| 2e 0a 5c 65 6e 64 7b 65 | 6e 75 6d 65 72 61 74 65 |..\end{e|numerate|
|000052c0| 7d 0a 0a 41 6c 74 68 6f | 75 67 68 20 74 68 65 20 |}..Altho|ugh the |
|000052d0| 70 72 6f 67 72 61 6d 6d | 69 6e 67 0a 66 61 63 69 |programm|ing.faci|
|000052e0| 6c 69 74 69 65 73 20 6f | 66 20 5c 54 65 58 7b 7d |lities o|f \TeX{}|
|000052f0| 20 68 61 72 64 6c 79 20 | 65 78 63 65 65 64 20 74 | hardly |exceed t|
|00005300| 68 65 20 61 62 69 6c 69 | 74 69 65 73 20 6f 66 20 |he abili|ties of |
|00005310| 61 20 54 75 72 69 6e 67 | 20 6d 61 63 68 69 6e 65 |a Turing| machine|
|00005320| 2c 0a 74 68 65 79 20 61 | 72 65 20 73 75 66 66 69 |,.they a|re suffi|
|00005330| 63 69 65 6e 74 20 74 6f | 0a 68 61 6e 64 6c 65 20 |cient to|.handle |
|00005340| 73 6d 61 6c 6c 20 70 72 | 6f 67 72 61 6d 73 2e 20 |small pr|ograms. |
|00005350| 48 6f 77 20 61 62 6f 75 | 74 20 74 68 65 20 67 72 |How abou|t the gr|
|00005360| 61 70 68 69 63 73 20 66 | 61 63 69 6c 69 74 69 65 |aphics f|acilitie|
|00005370| 73 3f 0a 41 6c 74 68 6f | 75 67 68 20 5c 54 65 58 |s?.Altho|ugh \TeX|
|00005380| 7b 7d 20 68 61 73 20 6e | 6f 20 62 75 69 6c 74 2d |{} has n|o built-|
|00005390| 69 6e 20 67 72 61 70 68 | 69 63 73 20 66 61 63 69 |in graph|ics faci|
|000053a0| 6c 69 74 69 65 73 2c 20 | 69 74 0a 61 6c 6c 6f 77 |lities, |it.allow|
|000053b0| 73 20 74 68 65 20 70 6c | 61 63 65 6d 65 6e 74 20 |s the pl|acement |
|000053c0| 6f 66 20 63 68 61 72 61 | 63 74 65 72 73 20 69 6e |of chara|cters in|
|000053d0| 20 61 72 62 69 74 72 61 | 72 79 20 70 6f 73 69 74 | arbitra|ry posit|
|000053e0| 69 6f 6e 73 20 6f 6e 0a | 74 68 65 20 70 61 67 65 |ions on.|the page|
|000053f0| 2e 20 54 68 65 72 65 66 | 6f 72 65 2c 20 63 6f 6d |. Theref|ore, com|
|00005400| 70 6c 65 78 20 70 69 63 | 74 75 72 65 73 20 63 61 |plex pic|tures ca|
|00005410| 6e 20 62 65 20 73 79 6e | 74 68 65 73 69 7a 65 64 |n be syn|thesized|
|00005420| 20 66 72 6f 6d 20 65 6c | 65 6d 65 6e 74 61 72 79 | from el|ementary|
|00005430| 0a 70 69 63 74 75 72 65 | 20 65 6c 65 6d 65 6e 74 |.picture| element|
|00005440| 73 20 74 72 65 61 74 65 | 64 20 61 73 20 63 68 61 |s treate|d as cha|
|00005450| 72 61 63 74 65 72 73 2e | 20 4c 61 6d 70 6f 72 74 |racters.| Lamport|
|00005460| 20 68 61 73 20 69 6e 63 | 6c 75 64 65 64 20 73 75 | has inc|luded su|
|00005470| 63 68 0a 61 20 70 69 63 | 74 75 72 65 20 64 72 61 |ch.a pic|ture dra|
|00005480| 77 69 6e 67 20 65 6e 76 | 69 72 6f 6e 6d 65 6e 74 |wing env|ironment|
|00005490| 20 69 6e 20 68 69 73 20 | 6d 61 63 72 6f 20 70 61 | in his |macro pa|
|000054a0| 63 6b 61 67 65 20 5c 4c | 61 54 65 58 2c 20 75 73 |ckage \L|aTeX, us|
|000054b0| 69 6e 67 0a 71 75 61 72 | 74 65 72 20 63 69 72 63 |ing.quar|ter circ|
|000054c0| 6c 65 73 20 6f 66 20 64 | 69 66 66 65 72 65 6e 74 |les of d|ifferent|
|000054d0| 20 73 69 7a 65 73 20 61 | 6e 64 20 6c 69 6e 65 20 | sizes a|nd line |
|000054e0| 73 65 67 6d 65 6e 74 73 | 20 28 77 69 74 68 20 61 |segments| (with a|
|000054f0| 6e 64 20 77 69 74 68 6f | 75 74 0a 61 72 72 6f 77 |nd witho|ut.arrow|
|00005500| 20 68 65 61 64 73 29 20 | 6f 66 20 64 69 66 66 65 | heads) |of diffe|
|00005510| 72 65 6e 74 20 73 6c 6f | 70 65 73 20 61 73 20 62 |rent slo|pes as b|
|00005520| 61 73 69 63 20 65 6c 65 | 6d 65 6e 74 73 3b 20 73 |asic ele|ments; s|
|00005530| 65 65 7e 5c 63 69 74 65 | 7b 4c 61 54 65 58 7d 2e |ee~\cite|{LaTeX}.|
|00005540| 0a 54 68 65 73 65 20 65 | 6c 65 6d 65 6e 74 73 20 |.These e|lements |
|00005550| 61 72 65 20 73 75 66 66 | 69 63 69 65 6e 74 20 66 |are suff|icient f|
|00005560| 6f 72 20 64 72 61 77 69 | 6e 67 20 74 72 65 65 73 |or drawi|ng trees|
|00005570| 2e 0a 0a 54 68 69 73 20 | 73 75 72 76 65 79 20 6f |...This |survey o|
|00005580| 66 20 5c 54 65 58 27 73 | 20 63 61 70 61 62 69 6c |f \TeX's| capabil|
|00005590| 69 74 69 65 73 20 69 6d | 70 6c 69 65 73 20 74 68 |ities im|plies th|
|000055a0| 61 74 20 5c 54 65 58 7b | 7d 20 6d 61 79 20 62 65 |at \TeX{|} may be|
|000055b0| 20 61 20 73 75 69 74 61 | 62 6c 65 0a 74 65 78 74 | a suita|ble.text|
|000055c0| 20 70 72 6f 63 65 73 73 | 69 6e 67 20 73 79 73 74 | process|ing syst|
|000055d0| 65 6d 20 74 6f 20 69 6d | 70 6c 65 6d 65 6e 74 20 |em to im|plement |
|000055e0| 61 20 74 72 65 65 20 64 | 72 61 77 69 6e 67 20 61 |a tree d|rawing a|
|000055f0| 6c 67 6f 72 69 74 68 6d | 20 64 69 72 65 63 74 6c |lgorithm| directl|
|00005600| 79 2e 0a 57 65 20 62 61 | 73 65 20 6f 75 72 20 61 |y..We ba|se our a|
|00005610| 6c 67 6f 72 69 74 68 6d | 20 6f 6e 20 74 68 65 20 |lgorithm| on the |
|00005620| 52 54 7e 61 6c 67 6f 72 | 69 74 68 6d 2c 20 62 65 |RT~algor|ithm, be|
|00005630| 63 61 75 73 65 20 74 68 | 69 73 20 61 6c 67 6f 72 |cause th|is algor|
|00005640| 69 74 68 6d 0a 67 69 76 | 65 73 2c 20 61 65 73 74 |ithm.giv|es, aest|
|00005650| 68 65 74 69 63 61 6c 6c | 79 2c 20 74 68 65 20 6d |heticall|y, the m|
|00005660| 6f 73 74 20 70 6c 65 61 | 73 69 6e 67 20 72 65 73 |ost plea|sing res|
|00005670| 75 6c 74 73 2e 20 49 6e | 20 74 68 65 20 66 69 72 |ults. In| the fir|
|00005680| 73 74 20 76 65 72 73 69 | 6f 6e 0a 70 72 65 73 65 |st versi|on.prese|
|00005690| 6e 74 65 64 20 68 65 72 | 65 2c 20 77 65 0a 72 65 |nted her|e, we.re|
|000056a0| 73 74 72 69 63 74 20 6f | 75 72 73 65 6c 76 65 73 |strict o|urselves|
|000056b0| 20 74 6f 20 75 6e 61 72 | 79 2d 62 69 6e 61 72 79 | to unar|y-binary|
|000056c0| 20 74 72 65 65 73 2c 20 | 61 6c 74 68 6f 75 67 68 | trees, |although|
|000056d0| 20 6f 75 72 20 6d 65 74 | 68 6f 64 20 69 73 0a 61 | our met|hod is.a|
|000056e0| 70 70 6c 69 63 61 62 6c | 65 20 74 6f 20 61 72 62 |pplicabl|e to arb|
|000056f0| 69 74 72 61 72 79 20 6d | 75 6c 74 69 77 61 79 20 |itrary m|ultiway |
|00005700| 74 72 65 65 73 2e 20 42 | 75 74 20 74 6f 20 74 61 |trees. B|ut to ta|
|00005710| 6b 65 20 61 64 76 61 6e | 74 61 67 65 0a 6f 66 20 |ke advan|tage.of |
|00005720| 74 68 65 20 74 65 78 74 | 20 70 72 6f 63 65 73 73 |the text| process|
|00005730| 69 6e 67 20 65 6e 76 69 | 72 6f 6e 6d 65 6e 74 2c |ing envi|ronment,|
|00005740| 20 77 65 20 65 78 70 61 | 6e 64 20 74 68 65 20 61 | we expa|nd the a|
|00005750| 6c 67 6f 72 69 74 68 6d | 20 74 6f 20 61 6c 6c 6f |lgorithm| to allo|
|00005760| 77 0a 6c 61 62 65 6c 65 | 64 20 6e 6f 64 65 73 2e |w.labele|d nodes.|
|00005770| 0a 0a 49 6e 20 63 6f 6e | 74 72 61 73 74 20 74 6f |..In con|trast to|
|00005780| 20 70 72 65 76 69 6f 75 | 73 20 74 72 65 65 20 64 | previou|s tree d|
|00005790| 72 61 77 69 6e 67 20 70 | 72 6f 67 72 61 6d 73 2c |rawing p|rograms,|
|000057a0| 20 77 65 20 66 65 65 6c | 20 6e 6f 20 6e 65 63 65 | we feel| no nece|
|000057b0| 73 73 69 74 79 20 74 6f | 0a 70 6f 73 69 74 69 6f |ssity to|.positio|
|000057c0| 6e 20 74 68 65 20 6e 6f | 64 65 73 20 6f 66 20 61 |n the no|des of a|
|000057d0| 20 74 72 65 65 20 6f 6e | 20 61 20 66 69 78 65 64 | tree on| a fixed|
|000057e0| 20 67 72 69 64 2e 20 57 | 68 69 6c 65 20 74 68 69 | grid. W|hile thi|
|000057f0| 73 20 6d 61 79 20 62 65 | 0a 72 65 61 73 6f 6e 61 |s may be|.reasona|
|00005800| 62 6c 65 20 66 6f 72 20 | 61 20 70 6c 6f 74 74 65 |ble for |a plotte|
|00005810| 72 20 77 69 74 68 20 61 | 20 63 6f 61 72 73 65 20 |r with a| coarse |
|00005820| 72 65 73 6f 6c 75 74 69 | 6f 6e 2c 20 69 74 20 69 |resoluti|on, it i|
|00005830| 73 20 63 65 72 74 61 69 | 6e 6c 79 20 6e 6f 74 0a |s certai|nly not.|
|00005840| 6e 65 63 65 73 73 61 72 | 79 20 66 6f 72 20 5c 54 |necessar|y for \T|
|00005850| 65 58 2c 20 61 20 73 79 | 73 74 65 6d 20 74 68 61 |eX, a sy|stem tha|
|00005860| 74 20 69 73 20 63 61 70 | 61 62 6c 65 20 6f 66 20 |t is cap|able of |
|00005870| 68 61 6e 64 6c 69 6e 67 | 0a 61 72 62 69 74 72 61 |handling|.arbitra|
|00005880| 72 79 20 64 69 6d 65 6e | 73 69 6f 6e 73 0a 61 6e |ry dimen|sions.an|
|00005890| 64 20 70 72 6f 64 75 63 | 69 6e 67 20 64 65 76 69 |d produc|ing devi|
|000058a0| 63 65 20 5c 65 6d 70 68 | 7b 69 6e 64 65 70 65 6e |ce \emph|{indepen|
|000058b0| 64 65 6e 74 7d 20 6f 75 | 74 70 75 74 2e 0a 0a 0a |dent} ou|tput....|
|000058c0| 5c 73 65 63 74 69 6f 6e | 7b 41 20 72 65 70 72 65 |\section|{A repre|
|000058d0| 73 65 6e 74 61 74 69 6f | 6e 20 6d 65 74 68 6f 64 |sentatio|n method|
|000058e0| 20 66 6f 72 20 5c 54 65 | 58 7b 7d 74 72 65 65 73 | for \Te|X{}trees|
|000058f0| 7d 0a 0a 54 68 65 20 66 | 69 72 73 74 20 70 72 6f |}..The f|irst pro|
|00005900| 62 6c 65 6d 20 74 6f 20 | 62 65 20 73 6f 6c 76 65 |blem to |be solve|
|00005910| 64 20 69 6e 20 69 6d 70 | 6c 65 6d 65 6e 74 69 6e |d in imp|lementin|
|00005920| 67 20 6f 75 72 20 74 72 | 65 65 20 64 72 61 77 69 |g our tr|ee drawi|
|00005930| 6e 67 20 61 6c 67 6f 72 | 69 74 68 6d 0a 69 73 20 |ng algor|ithm.is |
|00005940| 68 6f 77 20 74 6f 20 63 | 68 6f 6f 73 65 20 61 20 |how to c|hoose a |
|00005950| 67 6f 6f 64 20 69 6e 74 | 65 72 6e 61 6c 20 72 65 |good int|ernal re|
|00005960| 70 72 65 73 65 6e 74 61 | 74 69 6f 6e 0a 66 6f 72 |presenta|tion.for|
|00005970| 20 74 72 65 65 73 2e 20 | 41 20 73 74 72 61 69 67 | trees. |A straig|
|00005980| 68 74 66 6f 72 77 61 72 | 64 20 61 64 61 70 74 61 |htforwar|d adapta|
|00005990| 74 69 6f 6e 0a 6f 66 20 | 74 68 65 20 69 6d 70 6c |tion.of |the impl|
|000059a0| 65 6d 65 6e 74 61 74 69 | 6f 6e 20 62 79 20 52 65 |ementati|on by Re|
|000059b0| 69 6e 67 6f 6c 64 20 61 | 6e 64 20 54 69 6c 66 6f |ingold a|nd Tilfo|
|000059c0| 72 64 20 72 65 71 75 69 | 72 65 73 2c 20 66 6f 72 |rd requi|res, for|
|000059d0| 20 65 61 63 68 20 6e 6f | 64 65 2c 0a 61 74 20 6c | each no|de,.at l|
|000059e0| 65 61 73 74 3a 0a 25 0a | 5c 62 65 67 69 6e 7b 65 |east:.%.|\begin{e|
|000059f0| 6e 75 6d 65 72 61 74 65 | 7d 0a 5c 69 74 65 6d 20 |numerate|}.\item |
|00005a00| 74 77 6f 20 70 6f 69 6e | 74 65 72 73 20 74 6f 20 |two poin|ters to |
|00005a10| 74 68 65 20 63 68 69 6c | 64 72 65 6e 20 6f 66 20 |the chil|dren of |
|00005a20| 74 68 65 20 6e 6f 64 65 | 2c 0a 5c 69 74 65 6d 20 |the node|,.\item |
|00005a30| 74 77 6f 20 64 69 6d 65 | 6e 73 69 6f 6e 73 20 66 |two dime|nsions f|
|00005a40| 6f 72 20 74 68 65 20 6f | 66 66 73 65 74 20 74 6f |or the o|ffset to|
|00005a50| 20 74 68 65 20 6c 65 66 | 74 20 61 6e 64 20 74 68 | the lef|t and th|
|00005a60| 65 20 72 69 67 68 74 20 | 63 68 69 6c 64 20 28 74 |e right |child (t|
|00005a70| 68 65 73 65 0a 20 20 20 | 20 20 20 6d 61 79 20 62 |hese.   |   may b|
|00005a80| 65 20 64 69 66 66 65 72 | 65 6e 74 20 6f 6e 63 65 |e differ|ent once|
|00005a90| 20 74 68 65 72 65 20 61 | 72 65 20 6c 61 62 65 6c | there a|re label|
|00005aa0| 73 20 6f 66 20 64 69 66 | 66 65 72 65 6e 74 20 77 |s of dif|ferent w|
|00005ab0| 69 64 74 68 73 20 74 6f | 20 74 68 65 0a 20 20 20 |idths to| the.   |
|00005ac0| 20 20 20 6c 65 66 74 20 | 61 6e 64 20 72 69 67 68 |   left |and righ|
|00005ad0| 74 20 6f 66 20 74 68 65 | 20 6e 6f 64 65 73 29 2c |t of the| nodes),|
|00005ae0| 0a 5c 69 74 65 6d 20 74 | 77 6f 20 64 69 6d 65 6e |.\item t|wo dimen|
|00005af0| 73 69 6f 6e 73 20 66 6f | 72 20 74 68 65 20 24 78 |sions fo|r the $x|
|00005b00| 24 2d 20 61 6e 64 20 24 | 79 24 2d 63 6f 6f 72 64 |$- and $|y$-coord|
|00005b10| 69 6e 61 74 65 73 20 6f | 66 20 74 68 65 20 66 69 |inates o|f the fi|
|00005b20| 6e 61 6c 0a 20 20 20 20 | 20 20 70 6f 73 69 74 69 |nal.    |  positi|
|00005b30| 6f 6e 20 6f 66 20 74 68 | 65 20 6e 6f 64 65 73 2c |on of th|e nodes,|
|00005b40| 0a 5c 69 74 65 6d 20 74 | 68 72 65 65 20 6f 72 20 |.\item t|hree or |
|00005b50| 66 6f 75 72 20 6c 61 62 | 65 6c 73 2c 20 61 6e 64 |four lab|els, and|
|00005b60| 0a 5c 69 74 65 6d 20 6f | 6e 65 20 74 6f 6b 65 6e |.\item o|ne token|
|00005b70| 20 74 6f 20 73 74 6f 72 | 65 20 74 68 65 20 67 65 | to stor|e the ge|
|00005b80| 6f 6d 65 74 72 69 63 20 | 73 68 61 70 65 20 28 63 |ometric |shape (c|
|00005b90| 69 72 63 6c 65 2c 20 73 | 71 75 61 72 65 2c 20 66 |ircle, s|quare, f|
|00005ba0| 72 61 6d 65 64 20 74 65 | 78 74 2c 20 65 74 63 2e |ramed te|xt, etc.|
|00005bb0| 29 0a 20 20 20 20 20 20 | 6f 66 20 74 68 65 20 6e |).      |of the n|
|00005bc0| 6f 64 65 2e 0a 5c 65 6e | 64 7b 65 6e 75 6d 65 72 |ode..\en|d{enumer|
|00005bd0| 61 74 65 7d 0a 25 0a 42 | 65 63 61 75 73 65 20 74 |ate}.%.B|ecause t|
|00005be0| 68 65 73 65 20 64 61 74 | 61 20 61 72 65 20 75 73 |hese dat|a are us|
|00005bf0| 65 64 20 66 72 65 71 75 | 65 6e 74 6c 79 20 69 6e |ed frequ|ently in|
|00005c00| 20 63 61 6c 63 75 6c 61 | 74 69 6f 6e 73 2c 20 74 | calcula|tions, t|
|00005c10| 68 65 79 20 73 68 6f 75 | 6c 64 20 62 65 0a 73 74 |hey shou|ld be.st|
|00005c20| 6f 72 65 64 20 69 6e 20 | 72 65 67 69 73 74 65 72 |ored in |register|
|00005c30| 73 20 28 74 68 61 74 27 | 73 20 77 68 61 74 20 76 |s (that'|s what v|
|00005c40| 61 72 69 61 62 6c 65 73 | 20 61 72 65 20 63 61 6c |ariables| are cal|
|00005c50| 6c 65 64 20 69 6e 20 5c | 54 65 58 29 0a 72 61 74 |led in \|TeX).rat|
|00005c60| 68 65 72 20 74 68 61 6e | 20 62 65 69 6e 67 20 72 |her than| being r|
|00005c70| 65 63 6f 6d 70 75 74 65 | 64 2c 20 74 6f 20 6f 62 |ecompute|d, to ob|
|00005c80| 74 61 69 6e 0a 72 65 61 | 73 6f 6e 61 62 6c 79 20 |tain.rea|sonably |
|00005c90| 66 61 73 74 20 70 65 72 | 66 6f 72 6d 61 6e 63 65 |fast per|formance|
|00005ca0| 2e 20 54 68 69 73 20 67 | 69 76 65 73 20 61 20 74 |. This g|ives a t|
|00005cb0| 6f 74 61 6c 20 6f 66 20 | 24 31 30 4e 24 20 72 65 |otal of |$10N$ re|
|00005cc0| 67 69 73 74 65 72 73 20 | 66 6f 72 0a 61 20 74 72 |gisters |for.a tr|
|00005cd0| 65 65 20 77 69 74 68 20 | 24 4e 24 20 6e 6f 64 65 |ee with |$N$ node|
|00005ce0| 73 2c 20 77 68 69 63 68 | 20 71 75 69 63 6b 6c 79 |s, which| quickly|
|00005cf0| 20 65 78 63 65 65 64 73 | 0a 5c 54 65 58 27 73 20 | exceeds|.\TeX's |
|00005d00| 6c 69 6d 69 74 65 64 20 | 73 75 70 70 6c 79 20 6f |limited |supply o|
|00005d10| 66 20 72 65 67 69 73 74 | 65 72 73 2e 20 54 68 65 |f regist|ers. The|
|00005d20| 72 65 66 6f 72 65 2c 20 | 77 65 20 70 72 65 73 65 |refore, |we prese|
|00005d30| 6e 74 20 61 0a 6d 6f 64 | 69 66 69 65 64 20 61 6c |nt a.mod|ified al|
|00005d40| 67 6f 72 69 74 68 6d 20 | 68 61 6e 64 2d 74 61 69 |gorithm |hand-tai|
|00005d50| 6c 6f 72 65 64 20 74 6f | 20 74 68 65 20 61 62 69 |lored to| the abi|
|00005d60| 6c 69 74 69 65 73 20 6f | 66 20 5c 54 65 58 7b 7d |lities o|f \TeX{}|
|00005d70| 2e 0a 57 65 20 73 74 61 | 72 74 20 77 69 74 68 20 |..We sta|rt with |
|00005d80| 74 68 65 20 66 6f 6c 6c | 6f 77 69 6e 67 20 6f 62 |the foll|owing ob|
|00005d90| 73 65 72 76 61 74 69 6f | 6e 2e 0a 53 75 70 70 6f |servatio|n..Suppo|
|00005da0| 73 65 20 61 20 75 6e 61 | 72 79 2d 62 69 6e 61 72 |se a una|ry-binar|
|00005db0| 79 20 74 72 65 65 20 69 | 73 20 62 75 69 6c 74 20 |y tree i|s built |
|00005dc0| 62 6f 74 74 6f 6d 2d 75 | 70 2c 20 75 73 69 6e 67 |bottom-u|p, using|
|00005dd0| 20 61 20 70 6f 73 74 6f | 72 64 65 72 0a 74 72 61 | a posto|rder.tra|
|00005de0| 76 65 72 73 61 6c 2e 20 | 54 68 69 73 20 63 61 6e |versal. |This can|
|00005df0| 20 62 65 20 64 6f 6e 65 | 20 62 79 20 72 65 70 65 | be done| by repe|
|00005e00| 61 74 69 6e 67 20 74 68 | 65 20 66 6f 6c 6c 6f 77 |ating th|e follow|
|00005e10| 69 6e 67 20 74 68 72 65 | 65 20 73 74 65 70 73 20 |ing thre|e steps |
|00005e20| 69 6e 0a 61 6e 20 6f 72 | 64 65 72 20 64 65 74 65 |in.an or|der dete|
|00005e30| 72 6d 69 6e 65 64 20 62 | 79 20 74 68 65 20 74 72 |rmined b|y the tr|
|00005e40| 65 65 20 74 6f 20 62 65 | 20 62 75 69 6c 74 2e 0a |ee to be| built..|
|00005e50| 0a 5c 62 65 67 69 6e 7b | 65 6e 75 6d 65 72 61 74 |.\begin{|enumerat|
|00005e60| 65 7d 0a 5c 69 74 65 6d | 20 43 72 65 61 74 65 20 |e}.\item| Create |
|00005e70| 61 20 6e 65 77 20 73 75 | 62 74 72 65 65 20 63 6f |a new su|btree co|
|00005e80| 6e 73 69 73 74 69 6e 67 | 20 6f 66 20 6f 6e 65 20 |nsisting| of one |
|00005e90| 65 78 74 65 72 6e 61 6c | 20 6e 6f 64 65 2e 0a 5c |external| node..\|
|00005ea0| 69 74 65 6d 20 43 72 65 | 61 74 65 20 61 20 6e 65 |item Cre|ate a ne|
|00005eb0| 77 20 73 75 62 74 72 65 | 65 20 62 79 20 61 70 70 |w subtre|e by app|
|00005ec0| 65 6e 64 69 6e 67 20 74 | 68 65 20 74 77 6f 20 73 |ending t|he two s|
|00005ed0| 75 62 74 72 65 65 73 20 | 6c 61 73 74 20 63 72 65 |ubtrees |last cre|
|00005ee0| 61 74 65 64 20 0a 20 20 | 20 20 20 20 74 6f 20 61 |ated .  |    to a|
|00005ef0| 20 6e 65 77 20 62 69 6e | 61 72 79 20 6e 6f 64 65 | new bin|ary node|
|00005f00| 3b 20 73 65 65 20 5c 66 | 69 67 7b 43 6f 6e 73 74 |; see \f|ig{Const|
|00005f10| 72 75 63 74 7d 2e 0a 5c | 69 74 65 6d 20 43 72 65 |ruct}..\|item Cre|
|00005f20| 61 74 65 20 61 20 6e 65 | 77 20 73 75 62 74 72 65 |ate a ne|w subtre|
|00005f30| 65 20 62 79 20 61 70 70 | 65 6e 64 69 6e 67 20 74 |e by app|ending t|
|00005f40| 68 65 20 73 75 62 74 72 | 65 65 20 63 72 65 61 74 |he subtr|ee creat|
|00005f50| 65 64 20 6c 61 73 74 20 | 61 73 20 61 20 6c 65 66 |ed last |as a lef|
|00005f60| 74 2c 0a 20 20 20 20 20 | 20 72 69 67 68 74 2c 20 |t,.     | right, |
|00005f70| 6f 72 20 75 6e 61 72 79 | 20 73 75 62 74 72 65 65 |or unary| subtree|
|00005f80| 20 6f 66 20 61 20 6e 65 | 77 20 6e 6f 64 65 3b 20 | of a ne|w node; |
|00005f90| 73 65 65 20 5c 66 69 67 | 7b 43 6f 6e 73 74 72 75 |see \fig|{Constru|
|00005fa0| 63 74 7d 2e 0a 5c 65 6e | 64 7b 65 6e 75 6d 65 72 |ct}..\en|d{enumer|
|00005fb0| 61 74 65 7d 0a 0a 28 41 | 20 70 6f 69 6e 74 65 72 |ate}..(A| pointer|
|00005fc0| 20 74 6f 29 20 65 61 63 | 68 20 73 75 62 74 72 65 | to) eac|h subtre|
|00005fd0| 65 20 74 68 61 74 20 68 | 61 73 20 62 65 65 6e 0a |e that h|as been.|
|00005fe0| 63 72 65 61 74 65 64 20 | 69 6e 20 73 74 65 70 73 |created |in steps|
|00005ff0| 20 31 2d 2d 33 20 69 73 | 20 70 75 73 68 65 64 20 | 1--3 is| pushed |
|00006000| 6f 6e 74 6f 20 61 20 73 | 74 61 63 6b 2c 20 61 6e |onto a s|tack, an|
|00006010| 64 0a 73 74 65 70 73 20 | 32 20 61 6e 64 20 33 20 |d.steps |2 and 3 |
|00006020| 72 65 6d 6f 76 65 20 74 | 77 6f 20 74 72 65 65 73 |remove t|wo trees|
|00006030| 20 6f 72 20 6f 6e 65 20 | 74 72 65 65 2c 20 72 65 | or one |tree, re|
|00006040| 73 70 65 63 74 69 76 65 | 6c 79 2c 0a 66 72 6f 6d |spective|ly,.from|
|00006050| 20 74 68 65 20 73 74 61 | 63 6b 20 62 65 66 6f 72 | the sta|ck befor|
|00006060| 65 20 74 68 65 20 70 75 | 73 68 0a 6f 70 65 72 61 |e the pu|sh.opera|
|00006070| 74 69 6f 6e 20 69 73 20 | 63 61 72 72 69 65 64 20 |tion is |carried |
|00006080| 6f 75 74 2e 20 54 68 65 | 20 74 72 65 65 20 74 6f |out. The| tree to|
|00006090| 20 62 65 20 62 75 69 6c | 74 20 69 73 0a 74 68 65 | be buil|t is.the|
|000060a0| 20 74 72 65 65 20 72 65 | 6d 61 69 6e 69 6e 67 20 | tree re|maining |
|000060b0| 6f 6e 20 74 68 65 20 73 | 74 61 63 6b 2e 0a 0a 5c |on the s|tack...\|
|000060c0| 62 65 67 69 6e 7b 46 69 | 67 75 72 65 7d 0a 5c 63 |begin{Fi|gure}.\c|
|000060d0| 65 6e 74 65 72 69 6e 67 | 0a 5c 62 65 67 69 6e 7b |entering|.\begin{|
|000060e0| 54 72 65 65 7d 0a 5c 74 | 72 65 65 73 79 6d 62 6f |Tree}.\t|reesymbo|
|000060f0| 6c 7b 5c 6c 76 6c 73 7b | 32 7d 7d 25 0a 5c 68 73 |l{\lvls{|2}}%.\hs|
|00006100| 70 61 63 65 7b 2d 5c 6c | 40 73 74 6c 6d 6f 66 66 |pace{-\l|@stlmoff|
|00006110| 7d 5c 75 73 65 62 6f 78 | 7b 5c 6c 40 73 74 74 72 |}\usebox|{\l@sttr|
|00006120| 65 65 62 6f 78 7d 5c 68 | 73 70 61 63 65 7b 5c 6c |eebox}\h|space{\l|
|00006130| 40 73 74 72 6d 6f 66 66 | 7d 0a 24 2b 24 0a 5c 74 |@strmoff|}.$+$.\t|
|00006140| 72 65 65 73 79 6d 62 6f | 6c 7b 5c 6c 76 6c 73 7b |reesymbo|l{\lvls{|
|00006150| 32 7d 7d 25 0a 5c 68 73 | 70 61 63 65 7b 2d 5c 6c |2}}%.\hs|pace{-\l|
|00006160| 40 73 74 6c 6d 6f 66 66 | 7d 5c 75 73 65 62 6f 78 |@stlmoff|}\usebox|
|00006170| 7b 5c 6c 40 73 74 74 72 | 65 65 62 6f 78 7d 5c 68 |{\l@sttr|eebox}\h|
|00006180| 73 70 61 63 65 7b 5c 6c | 40 73 74 72 6d 6f 66 66 |space{\l|@strmoff|
|00006190| 7d 5c 71 75 61 64 0a 24 | 5c 4c 6f 6e 67 72 69 67 |}\quad.$|\Longrig|
|000061a0| 68 74 61 72 72 6f 77 24 | 5c 71 75 61 64 0a 5c 74 |htarrow$|\quad.\t|
|000061b0| 72 65 65 73 79 6d 62 6f | 6c 7b 5c 6c 76 6c 73 7b |reesymbo|l{\lvls{|
|000061c0| 32 7d 7d 25 0a 5c 74 72 | 65 65 73 79 6d 62 6f 6c |2}}%.\tr|eesymbol|
|000061d0| 7b 5c 6c 76 6c 73 7b 32 | 7d 7d 25 0a 5c 6e 6f 64 |{\lvls{2|}}%.\nod|
|000061e0| 65 7b 5c 74 79 70 65 7b | 64 6f 74 7d 7d 25 0a 5c |e{\type{|dot}}%.\|
|000061f0| 68 73 70 61 63 65 7b 2d | 5c 6c 40 73 74 6c 6d 6f |hspace{-|\l@stlmo|
|00006200| 66 66 7d 5c 72 61 69 73 | 65 62 6f 78 7b 5c 76 64 |ff}\rais|ebox{\vd|
|00006210| 40 73 74 7d 7b 5c 75 73 | 65 62 6f 78 5c 6c 40 73 |@st}{\us|ebox\l@s|
|00006220| 74 74 72 65 65 62 6f 78 | 7d 5c 68 73 70 61 63 65 |ttreebox|}\hspace|
|00006230| 7b 5c 6c 40 73 74 72 6d | 6f 66 66 7d 25 0a 5c 65 |{\l@strm|off}%.\e|
|00006240| 6e 64 7b 54 72 65 65 7d | 0a 0a 5c 76 73 6b 69 70 |nd{Tree}|..\vskip|
|00006250| 5c 62 61 73 65 6c 69 6e | 65 73 6b 69 70 0a 0a 5c |\baselin|eskip..\|
|00006260| 62 65 67 69 6e 7b 54 72 | 65 65 7d 0a 5c 74 72 65 |begin{Tr|ee}.\tre|
|00006270| 65 73 79 6d 62 6f 6c 7b | 5c 6c 76 6c 73 7b 32 7d |esymbol{|\lvls{2}|
|00006280| 7d 25 0a 5c 68 73 70 61 | 63 65 7b 2d 5c 6c 40 73 |}%.\hspa|ce{-\l@s|
|00006290| 74 6c 6d 6f 66 66 7d 5c | 75 73 65 62 6f 78 7b 5c |tlmoff}\|usebox{\|
|000062a0| 6c 40 73 74 74 72 65 65 | 62 6f 78 7d 5c 68 73 70 |l@sttree|box}\hsp|
|000062b0| 61 63 65 7b 5c 6c 40 73 | 74 72 6d 6f 66 66 7d 5c |ace{\l@s|trmoff}\|
|000062c0| 71 75 61 64 0a 24 5c 4c | 6f 6e 67 72 69 67 68 74 |quad.$\L|ongright|
|000062d0| 61 72 72 6f 77 24 5c 71 | 75 61 64 0a 5c 74 72 65 |arrow$\q|uad.\tre|
|000062e0| 65 73 79 6d 62 6f 6c 7b | 5c 6c 76 6c 73 7b 32 7d |esymbol{|\lvls{2}|
|000062f0| 7d 25 0a 5c 6e 6f 64 65 | 7b 5c 6c 65 66 74 6f 6e |}%.\node|{\lefton|
|00006300| 6c 79 5c 74 79 70 65 7b | 64 6f 74 7d 7d 25 0a 5c |ly\type{|dot}}%.\|
|00006310| 68 73 70 61 63 65 7b 2d | 5c 6c 40 73 74 6c 6d 6f |hspace{-|\l@stlmo|
|00006320| 66 66 7d 5c 72 61 69 73 | 65 62 6f 78 7b 5c 76 64 |ff}\rais|ebox{\vd|
|00006330| 40 73 74 7d 7b 5c 75 73 | 65 62 6f 78 5c 6c 40 73 |@st}{\us|ebox\l@s|
|00006340| 74 74 72 65 65 62 6f 78 | 7d 5c 68 73 70 61 63 65 |ttreebox|}\hspace|
|00006350| 7b 5c 6c 40 73 74 72 6d | 6f 66 66 7d 25 0a 5c 71 |{\l@strm|off}%.\q|
|00006360| 75 61 64 20 6f 72 5c 71 | 75 61 64 0a 5c 74 72 65 |uad or\q|uad.\tre|
|00006370| 65 73 79 6d 62 6f 6c 7b | 5c 6c 76 6c 73 7b 32 7d |esymbol{|\lvls{2}|
|00006380| 7d 25 0a 5c 6e 6f 64 65 | 7b 5c 75 6e 61 72 79 5c |}%.\node|{\unary\|
|00006390| 74 79 70 65 7b 64 6f 74 | 7d 7d 25 0a 5c 68 73 70 |type{dot|}}%.\hsp|
|000063a0| 61 63 65 7b 2d 5c 6c 40 | 73 74 6c 6d 6f 66 66 7d |ace{-\l@|stlmoff}|
|000063b0| 5c 72 61 69 73 65 62 6f | 78 7b 5c 76 64 40 73 74 |\raisebo|x{\vd@st|
|000063c0| 7d 7b 5c 75 73 65 62 6f | 78 5c 6c 40 73 74 74 72 |}{\usebo|x\l@sttr|
|000063d0| 65 65 62 6f 78 7d 5c 68 | 73 70 61 63 65 7b 5c 6c |eebox}\h|space{\l|
|000063e0| 40 73 74 72 6d 6f 66 66 | 7d 25 0a 5c 71 75 61 64 |@strmoff|}%.\quad|
|000063f0| 20 6f 72 5c 71 75 61 64 | 0a 5c 74 72 65 65 73 79 | or\quad|.\treesy|
+--------+-------------------------+-------------------------+--------+--------+